"Anchors" as pseudo-persistent positions

[Ville M. Vainio]

Due to Terry's problems with doDeleteNode (problem I faced a long time
go, but shrugged under the roof), I was thinking of the possibility of
a new "anchor" type.

Anchor would be a bit like position, but it would only consist of:

- parent vnode
- child index.
- (optional, for assertion) vnode

Every anchor created would be stored in global data structure in c.
inserting and deleting nodes would have to check all anchors applying
to current node, and adjust the anchor in appropriate fashion
(increment or decrement child index).

These would be analogous to emacs "mark" and "point", which move when
text is inserted/deleted.

Of course having many anchors would slow down Leo, so anchors should
be disposed at earliest possible opportunity. Typically within the
function that is creating the anchors.

Api would be like:

a1 = p1.anchor()
a2 = p2.anchor()

p1.doDelete()

pos = a2.position()
pos.doDelete() # works reliably!

of course a2.position() would not return the exact original p1 if
there are clones along the road, but it would still return something
that can be used to manipulate the tree. Alternative would be to move
lots of position api to anchor, but that would be a big change & lots
of work.

PS. codewise rocks. Just now I entered "codewise m position" on
command line to check what methods 'position' had, to ensure that it
was called doDelete()

--
Ville M. Vainio
http://tinyurl.com/vainio

[Terry Brown]

On Wed, 9 Dec 2009 22:01:40 +0200
"Ville M. Vainio" <viva...@gmail.com> wrote:

> Every anchor created would be stored in global data structure in c.
> inserting and deleting nodes would have to check all anchors applying
> to current node, and adjust the anchor in appropriate fashion
> (increment or decrement child index).

So these are backreferences?

Cheers -Terry

[vivainio]

Yes, if you want to call them that

----- Original message -----

So these are backreferences?

[Edward K. Ream]

On Wed, Dec 9, 2009 at 3:01 PM, Ville M. Vainio <viva...@gmail.com> wrote:
> Due to Terry's problems with doDeleteNode (problem I faced a long time
> go, but shrugged under the roof), I was thinking of the possibility of
> a new "anchor" type.

I would rather not do this. It is a half measure.

The essence of the difficulty is capture by the low-level method
p._adjustPositionBeforeUnlink. This complication can never go away,
but it can be hidden. Imo, it is no good trying to solve this problem
at the vnode level: we need position information for every
to-be-deleted node.

As I write this, it occurs to me that something like
p.deleteListOfPositions would be the best way to solve this problem.
Given the complexities, this method is more than just a convenience.

Edward

[Edward K. Ream]

On Thu, Dec 10, 2009 at 9:08 AM, Edward K. Ream <edre...@gmail.com> wrote:

> p.deleteListOfPositions would be the best way to solve this problem.
> Given the complexities, this method is more than just a convenience.

I'll work on this and let you know the results.

Edward

[Edward K. Ream]

On Thu, Dec 10, 2009 at 9:19 AM, Edward K. Ream <edre...@gmail.com> wrote:

>> p.deleteListOfPositions would be the best way to solve this problem.
>> Given the complexities, this method is more than just a convenience.
>
> I'll work on this and let you know the results.

We want p.deleteListOfPositions to be O(n), where n is the number of
to-be-deleted nodes, *not* the total number of nodes in the outline.
But this might be a vain hope.

For example, the first idea that comes to mind is to sort the
to-be-deleted nodes in outline order, then delete in reverse order.
But this will not work in general. Because of clones, there is no
ordering of nodes that will ensure that we can delete nodes "from back
to front". So the problem is non-trivial.

Edward

[Edward K. Ream]

On Thu, Dec 10, 2009 at 9:48 AM, Edward K. Ream <edre...@gmail.com> wrote:

> Because of clones, there is no ordering of nodes that will ensure that we can delete nodes "from back to front".

It looks like I have got this exactly wrong :-) This statement would
be true if we were deleting *nodes*, but we are deleting *positions*.
Which shows, I think, why we should be thinking positions, not nodes.

So it looks like the next task is to write p.sortListOfPositions().
Alternatively, we could require that the list of positions given to
p.deleteListOfPositions be already sorted: it will often be naturally
sorted. But we may as well do the whole job.

Edward

[Edward K. Ream]

On Thu, Dec 10, 2009 at 9:55 AM, Edward K. Ream <edre...@gmail.com> wrote:

> So it looks like the next task is to write p.sortListOfPositions().

Ha. The position class already contains the __eq__ and __ne__
methods. If we add the __lt__, __gt__, __le__ and __ge__ methods to
the position class, we can use Python's sort method to sort a list of
positions. Furthermore, the __le__ and __ge__ methods can be defined
in terms of the other "rich comparison" methods.

Isn't Python grand: we are reducing the problem to its essence in a
completely natural way. So now all we have to do is define __gt__ and
__lt__ so that p1 < p2 iff p1 appears before p2 in outline order.

Edward

[Ville M. Vainio]

On Thu, Dec 10, 2009 at 5:07 PM, Edward K. Ream <edre...@gmail.com> wrote:

> Ha.  The position class already contains the __eq__ and __ne__
> methods.  If we add the __lt__, __gt__, __le__ and __ge__ methods to
> the position class, we can use Python's sort method to sort a list of
> positions.  Furthermore, the __le__ and __ge__ methods can be defined
> in terms of the other "rich comparison" methods.
>
> Isn't Python grand: we are reducing the problem to its essence in a
> completely natural way.  So now all we have to do is define __gt__ and
> __lt__ so that p1 < p2 iff p1 appears before p2 in outline order.

When thinking of anchors, I was also thinking of insertion. Deletion
is indeed simpler.

If we are only thinking of deletion, you can specialize the anchor
approach nicely:

- create list of (parent_vnode, childindex)
- sort it (tuple sort does it)
- delete all in list

[Terry Brown]

On Thu, 10 Dec 2009 17:18:10 +0200

"Ville M. Vainio" <viva...@gmail.com> wrote:

> If we are only thinking of deletion, you can specialize the anchor
> approach nicely:
>
> - create list of (parent_vnode, childindex)
> - sort it (tuple sort does it)
> - delete all in list

I don't think you can assume a list of positions are all siblings.
contextmenu.py makes this selection possible:

X
X
X *
X *
X *
X *
X *
X *
X *
X *
X

where Xs are nodes, * indicates selection, and people who use
proportional fonts for email get what they deserve :-)

Hey - would it be cool to have an email system which lets you write in
rst and then sends both text (rst) and html forms...

Cheers -Terry

[Ville M. Vainio]

On Thu, Dec 10, 2009 at 6:46 PM, Terry Brown <terry_...@yahoo.com> wrote:

> I don't think you can assume a list of positions are all siblings.
> contextmenu.py makes this selection possible:

Yeah, but that won't break it if you are using vnodes - since you can
remove children from a vnode that has already been removed from a tree
safely.

The one problem I can think of is undo support.

[Terry Brown]

On Thu, 10 Dec 2009 19:04:16 +0200

"Ville M. Vainio" <viva...@gmail.com> wrote:

> The one problem I can think of is undo support.

Which is really nice with commands like "delete" :-)

Cheers -Terry

[Edward K. Ream]

On Dec 10, 10:07 am, "Edward K. Ream" <edream...@gmail.com> wrote:

> So now all we have to do is define __gt__ and
> __lt__ so that p1 < p2 iff p1 appears before p2 in outline order.

Rev 2551 of the leo-3k branch contains the following definition of
__gt__. Everything else can be computed from __gt__ and/or __eq__.
There is an exhaustive test in test.leo.

def __gt__ (self,other):
stack1,stack2 = self.stack,other.stack
n1,n2 = len(stack1),len(stack2)
n = min(n1,n2)
# compare the common stacks.
for i in range(n):
item1,item2 = stack1[i],stack2[i]
v1,x1 = item1 ; v2,x2 = item2
if x1 > x2: return True
elif x1 < x2: return False
# Finish the comparison.
if n1 == n2:
x1,x2 = self._childIndex,other._childIndex
return x1 > x2
elif n1 < n2:
v1,x1 = self.v,self._childIndex
v2,x2 = other.stack[n]
return x1 > x2
else:
return True

This was tricky to get right because of surprising asymmetries.

Edward

[Terry Brown]

Important

You should try and view the HTML version of this message!

On Thu, 10 Dec 2009 10:46:05 -0600 Terry Brown <terry_...@yahoo.com> wrote:

> Hey - would it be cool to have an email system which lets you write
> in rst and then sends both text (rst) and html forms...

Despite the fact y'all failed to chorus "Yes it would" ;-) I went ahead and set it up in Claws-mail

1. Add an rst-preview button to the Claws-mail compose window. It just runs a user command on the body text:

   | rst2pyg >~/.tmp.html; x-www-browser ~/.tmp.html
   

   rst2pyg is included below.

2. Add an indent button to the Claws-mail compose window. It just runs a user command on the selected text:

   | sed 's/^/  /' |
   

3. Write rst2email, included below.

4. Use Send Later for messages you want to process, so rst2email can get at them in the queue directory.

5. You can get rst2email_pygments.py (as imported by both rst2email and rst2pyg) from my blog, it's the file at the end of this page.

rst2email

#!/usr/bin/python
"""rst2email - look for messages in an email queue folder and
add an html part by processing the text part as rst

Terry Brown, terry_...@yahoo.com
"""

import email
import mailbox
from email.mime.text import MIMEText
from docutils.core import publish_string

# this import adds the sourcecode:: directive to rst
import rst2email_pygments

queue = "/home/tbrown/Mail/queue"

mbox = mailbox.MH(queue, email.message_from_file)

for msgkey in mbox.iterkeys():
    # d = email.utils.parsedate(msg.get('Date'))

    msg = mbox[msgkey]

    if not msg.is_multipart():
        txt = msg.get_payload()
        html = publish_string(txt, writer_name='html')
        part1 = MIMEText(txt, 'plain')
        part2 = MIMEText(html, 'html')
        part1["X-rst2email"] = "rst"
        part2["X-rst2email"] = "html"
        msg.set_type("multipart/alternative")
        msg.set_payload([])
        msg.attach(part1)
        msg.attach(part2)
        mbox[msgkey] = msg
    else:
        txtpart = None
        htmlpart = None
        for part in msg.walk():
            if part.get_content_type() == "text/plain":
                if txtpart:  # can't handle more than one
                    txtpart = None
                    break
                txtpart = part
            if part.get_content_type() == "text/html":
                if htmlpart:  # can't handle more than one
                    htmlpart = None
                    break
                htmlpart = part
        if txtpart and htmlpart and not txtpart.is_multipart():
            htmlpart.set_payload(
                publish_string(txtpart.get_payload(),
writer_name='html')) txtpart["X-rst2email"] = "rst"
            htmlpart["X-rst2email"] = "html"
            msg.set_type("multipart/alternative")
            mbox[msgkey] = msg

rst2pyg

1 2 3 4 5 6 7

#!/usr/bin/python from docutils.core import publish_string import rst2email_pygments import sys print publish_string(sys.stdin.read(), writer_name='html')

[Edward K. Ream]

On Dec 10, 2:53 pm, "Edward K. Ream" <edream...@gmail.com> wrote:

> Rev 2551 of the leo-3k branch contains the following definition of
> __gt__.  

Walking on the beach this morning, I realized that the actual problem
we are trying to solve has nothing to do either with clones or
positions! So yesterday's work on sorting positions is merely a
"Wittengenstein's ladder" that is to be thrown away once used :-)

When I began the walk, I had not intended to consider this problem,
but the mind sometimes has its own logic. First of all, I began to
think about clones and how they affect positions when we insert or
delete nodes. I soon realized that my train of thought from yesterday
was infected with old thinking about clones. In the present (one-
node) world, **there is no such thing as a cloned node**. There are
only multiple links to a node. Repeat after me: **all clones are the
same node**.

It is true that inserting, deleting or moving a node will change the
positions of all nodes following the changed node, but it turns out
that this doesn't help us solve the problem. In particular, sorting
positions and applying changes in reverse order will not work!

The proper way to understand the "batch change" problem is, as has
been hinted by others, to consider the changes at the (v)node level.
But as we shall soon see, anchors or other "mnemonic" devices will not
work either.

The proper way to think of any change to the outline is to take links
from parents to children into account. Fundamentally, there are only
two operations:

- Link (insert) a node as the n'th child of a parent.
- Unlink (delete) a node that appears as the n'th child of a parent.

Internally, moves are an unlink operation followed by a link. Low-
level operations always use link/unlink terminology: because of undo,
nothing is ever permanently deleted.

We are now in a position to see the actual problem. If we are given a
list of link/unlink operations to be applied to an outline, we can
apply those operations in *any* order if all the parent nodes are
different. The problem arises if we have two or more operations that
apply to the *same parent*. In this case, the order in which we apply
the operations matters, because the child index, n, may change as the
result of the operation.

We can see now that the problem has nothing to do with either clones
or positions. An example should make this clear. Let p be a parent
node, and child1 and child2 be children of p with child indices n1 and
n2 initially. (p will be the hidden root node if child1 or chile2 is
a top-level node). Suppose n1 < n2 and suppose we have a batch
operation consisting of the list:

[unlink child of p at n1, unlink child of p at n2]

**Important** The list does not specify child1 or child2 directly, but
only as the children of p at the given child indices. This side-steps
the "cloned siblings" problem, that is, the complication that would
arise if child1 == child2.

The essence of the problem is that we don't know what the second
operation means until we decide whether n2 refers to the child index
before or after the first operation is completed!

Do you see? Understood correctly, this is a very simple problem. The
solution will be to group operations by parent nodes, and then by
*ordered* operations on the children of that node. If there is only
one such child, we do the operation. If there are multiple children,
we do the operations in an *agreed upon* order, so that we know what
n1 and n2 mean.

Consider again, our batch operation list:

[unlink child of p at n1, unlink child of p at n2]

It will probably be most natural for n2 to mean the child index of
child2 *before* unlinking child1 from the parent p. This is most
natural because the (plugin) code that creates the batch operation
list can do so "naively", without worrying about the details. Given
this agreed-upon meaning of n2, Leo can safely do all operations by
sorting all operations (for a single parent) on the child indices, and
then doing the operations in reverse order.

I think this is, really and truly, the solution to the problem. We
have come a long way from convenience methods :-) All comments
welcome.

Edward

P.S. I haven't explicitly said why neither anchors nor positions will
solve the problem, but the reason should be clear enough: the
fundamental solution is to sort the operations of the children of one
particular parent. Neither anchors nor positions relate to this
fundamental solution.

EKR

[Ville M. Vainio]

On Fri, Dec 11, 2009 at 3:43 PM, Edward K. Ream <edre...@gmail.com> wrote:

> Do you see?  Understood correctly, this is a very simple problem. The
> solution will be to group operations by parent nodes, and then by
> *ordered* operations on the children of that node.  If there is only

Indeed, and to quote earlier email:

QQQ

If we are only thinking of deletion, you can specialize the anchor
approach nicely:

- create list of (parent_vnode, childindex)
- sort it (tuple sort does it)
- delete all in list

QQQ

You can think of "anchors" not as a datatype in its own right, but a
pair of (parent_vnode, childindex).

That structure is sort of "position-lite", and is sufficient
abstraction of "position" for most (all?) outline manipulation
operations.

Now, if we are thinking of outline *traversal*, anchor is not
sufficient since you may want to know the earlier parents.

[Edward K. Ream]

On Fri, Dec 11, 2009 at 9:07 AM, Ville M. Vainio <viva...@gmail.com> wrote:
> On Fri, Dec 11, 2009 at 3:43 PM, Edward K. Ream <edre...@gmail.com> wrote:
>
>> Do you see?  Understood correctly, this is a very simple problem. The
>> solution will be to group operations by parent nodes, and then by
>> *ordered* operations on the children of that node.  If there is only
>
> Indeed, and to quote earlier email:
>
> QQQ
>
> If we are only thinking of deletion, you can specialize the anchor
> approach nicely:
>
> - create list of (parent_vnode, childindex)
> - sort it (tuple sort does it)
> - delete all in list

> You can think of "anchors" not as a datatype in its own right, but a
> pair of (parent_vnode, childindex).

I agree. This is close to the solution I envisage. The next step is
to create a general way of specifying what I called the "batch
operation list". If we use the "naive" interpretation of child
indices (the indices before any operations have been applied), we may
as well just store the batch operation list as a tuple
(operation,position).

The "optimization" position -> (parent_vnode,childIndex) is an
implementation detail of no concern to the user/api. Given a list of
(operation,position) pairs, we will create a dictionary whose keys are
(parent) vnodes and whose values are lists of tuples
(operation,childIndex). We do the operations on the parents in any
order. For any particular parent, we do the operations in reverse
childIndex order.

Edward

[Ville M. Vainio]

On Fri, Dec 11, 2009 at 4:32 PM, Edward K. Ream <edre...@gmail.com> wrote:

> The "optimization" position -> (parent_vnode,childIndex) is an
> implementation detail of no concern to the user/api. Given a list of

Apiwise, "position" knows a lot more than vnode - for some use cases
it's more information than is needed for the operation at hand (also,
position can point to a completely wrong position, e.g. when created
by vnode2position - the user can be mislead to assume that the
position so created has reliable information, even when it only has
reliable information for particular api calls (ones where vnode +
index would be enough).

vnodes have the advantage that they, unlike positions, can be
"remembered" without knowing much about the outline by just storing
gnx (e.g. in plugins). Vnodes also won't catastrophically disappear
when you insert one node (again for the benefit of plugins).

[Edward K. Ream]

On Fri, Dec 11, 2009 at 9:32 AM, Edward K. Ream <edre...@gmail.com> wrote:

> We do the operations on the parents in any order. For any particular parent, we do the operations in reverse childIndex order.

This works for inserts and deletes: moves are more complex, because
the "unlink" portion of a move must happen before the "link". It's
doable, but perhaps just limiting operations to inserts and deletes
will suffice.

What do you think, amigos?

Edward

[Edward K. Ream]

What you say is true, but I think passing positions to
c.makeBatchChanges is simplest. Furthermore, the pair
(parent_vnode,childIndex) can change meanings as the result of changes
to the outline.

I'm not ruling out the anchor data type completely, but imo they
aren't as useful as you seem to think. There is no way for data to
change the fact that positions (or any possible proxy) can become
invalid when the outline changes.

Edward

[Terry Brown]

On Fri, 11 Dec 2009 10:38:46 -0500
"Edward K. Ream" <edre...@gmail.com> wrote:

> This works for inserts and deletes: moves are more complex, because
> the "unlink" portion of a move must happen before the "link". It's
> doable, but perhaps just limiting operations to inserts and deletes
> will suffice.

Thinking about multi-node cut / paste (i.e. a move?) I've been thinking
that all the stuff being cut could be temporarily "stored" off tree (I
was thinking appended to a special off tree node, but probably just
placed in a list would do), and then all copied to the destination from
that place. So I don't see unlink before link as being a problem.

Will need to watch, with cut, that the qt tree lets you select parents
and children at the same time. I don't think we want to prevent that,
it makes sense for delete, mark, etc., but for cut you only need to cut
the parents to the clipboard, obviously the children are coming with
them, and processing the children would just mess things up.

> What do you think, amigos?

I was going to say I wish I was close to beach, but of course I am, it
just happens to be a beach with an air temperature around -3 F
(-19 C) :)

Also I thought the code you made yesterday was sorting things to work
in reverse order? I think you're correct that clones are irrelevant
here, kind of amusing it took so long for that to become apparent :-)

Cheers -Terry

[Edward K. Ream]

On Fri, Dec 11, 2009 at 11:05 AM, Terry Brown <terry_...@yahoo.com> wrote:

> Thinking about multi-node cut / paste (i.e. a move?) I've been thinking
> that all the stuff being cut could be temporarily "stored" off tree (I
> was thinking appended to a special off tree node, but probably just
> placed in a list would do), and then all copied to the destination from
> that place.  So I don't see unlink before link as being a problem.

Hmm. I want to retain Leo's fundamental insert/delete link/unlink
code. Copying trees "offline" will create other complications, and
I'd really like to avoid those.

> Will need to watch, with cut, that the qt tree lets you select parents
> and children at the same time.  I don't think we want to prevent that,
> it makes sense for delete, mark, etc., but for cut you only need to cut
> the parents to the clipboard, obviously the children are coming with
> them, and processing the children would just mess things up.

Maybe this is a harder problem than I thought at first.

> I was going to say I wish I was close to beach, but of course I am, it
> just happens to be a beach with an air temperature around -3 F
> (-19 C) :)

Heh, heh, and two days ago it was too hot and humid here.

> Also I thought the code you made yesterday was sorting things to work
> in reverse order?

True, but it turns out that that approach was wrong. It's not
positions that need to be sorted, but children of a common parent.

> I think you're correct that clones are irrelevant
> here, kind of amusing it took so long for that to become apparent :-)

Yes, it is amusing. Happily, the present one-node world makes things
as simple as they can possibly be, but some complications are
unavoidable.

My take-away message from your comments is that c.doBatchOperations,
which I am in the midst of writing, had best take more care. It can't
blithely assume that operations on parent vnodes can be done in any
order. The first draft may make that assumption, but the second draft
had better check the batch operations list more carefully.

Edward

[Ville M. Vainio]

On Thu, Dec 10, 2009 at 11:28 PM, Terry Brown <terry_...@yahoo.com> wrote:

Important

You should try and view the HTML version of this message!

Right.

This kind of stuff makes me think html email is actually a somewhat tolerable concept.

For thunderbird, there is pasteCode:

https://addons.mozilla.org/en-US/thunderbird/addon/4046

-- 

[Terry Brown]

On Thu, 17 Dec 2009 13:52:08 +0200

"Ville M. Vainio" <viva...@gmail.com> wrote:

> This kind of stuff makes me think html email is actually a somewhat
> tolerable concept.

Maybe :-) even as I wrote it it was more because I thought email
rendered (to html) from rst was cool, rather than that I think html
email is necessary. It's funny looking at postings in this list vs. my
main inbox, here very very few msgs have html parts, whereas in the
main inbox at least 50% do.

Did occur to me that it would probably be possibly to set up some
combination of unicode chrs and css which would render leo trees
nicely in an html email.

Cheers -Terry