Subject: Re: [imapext] Problem with reusing untagged COPYUID in pipelined UID MOVE or MOVE

From: Jan Kundrát <[email-masked]>
Date: Sat, 01 Sep 2012 12:24:00 +0200

On 09/01/12 04:24, Ned Freed wrote:
> But in a way this is all moot. Even if this section didn't exist we can
> apply whatever restrictions we want to MOVE. The fact that this section
> exists
> is only an indication that there is ample precedent in IMAP for having such
> restrictions.

Ned, I agree. What I'm saying is that UID MOVE, as defined in -01, can 
have surprising results when pipelined, and am seeking a solution to fix 
this. If the solution ends up as "don't pipeline UID MOVE" *and* this is 
clearly documented in the draft, that will be acceptable to me, even if 
I still believe that there are ways to make this case safe and without 
any ambiguity while enabling pipelining.

> Doesn't follow. If the semantics and capabilities of a COPY/STORE/EXPUNGE
> sequence were identical to MOVE, there would be no need for MOVE. But
> the semantics rather obviously aren't the same.

Please keep in mind that I have never discussed MOVE, just UID MOVE. 
Everything I said about the ambiguity applies to UID MOVE, I've been 
ignoring MOVE altogether.

The draft says this:

>    The UID MOVE command has the same effect as a sequence of UID COPY,
>    UID STORE +FLAGS.SILENT \DELETED and UID EXPUNGE, with the added
>    requirement that each message SHOULD either be moved or unaffected.
>    The server SHOULD NOT leave a message in neither or both mailboxes
>    afterwards (even if the server returns a tagged NO response).
>
>    UID MOVE is the same as the three-command sequence in all other
>    respects, which implies that extensions which affect the three-
>    command sequence also affect UID MOVE, and that response codes such
>    as COPYUID, TRYCREATE and so on should be sent as appropriate.

To me, this means that if one can pipeline two occurences of a (UID 
COPY, UID STORE, UID EXPUNGE) sequence, it would be a very unexpected 
side effect if one could not pipeline two UID MOVE commands. It looks 
like Timo agrees with me on this one.

> Then the first question that needs to be asked is whether or not pipelining
> overlapping moves is a capability with a either a significant use-case
> of its
> own or is something that comes up willy-nilly and is also difficult for
> clients
> to avoid.
>
> Once that is asssed the costs of addressing the issue can be weighed
> against
> the benefits that will accrue in the client space.

Again, I agree completely. Let's ban UID MOVE pipelining or make it safe 
to pipeline. Either will work for me.

> And no, I don't care if there is concern that it might come up sometime or
> somewhere. The IMAP extensions space has quite a few examples of extensions
> that were made overly complex precisely because of this sort of vague
> concern.
> That's why this work was chartered as a narrowly focused effort.

My client uses pipelining aggressively. Copying and moving is handled by 
the same code path. Immediately after a mouse drag is performed, no 
matter whether there's another UID COPY in progress, an auxiliary "task" 
is instantiated. If the current operation is to "move messages", a 
second task for UID STORE is created and marked as depending on the 
first, copying one, and a third task which will eventually do UID 
EXPUNGE is created and marked as depending on the second one. The first 
task doing the UID COPY is activated more or less instantly.

There's a generic framework which is responsible for activating the 
depending tasks only when their dependency has finished successfully 
(i.e. one can only call UID FETCH after the mailbox has been selected, 
one can SELECT only after the LOGIN has completed, etc). It will "kill" 
those tasks whose parents have not succeeded. This layer is common to 
all commands.

Now, what happens when there's a slow network being involved and the 
user moves mouse fast enough? Due to the ordering of the tasks I've 
mentioned earlier, the communication might look like the following:

C: y1 UID COPY 2 foo
# UID STORE and UID EXPUNGE are pending on y1's completion
C: y2 UID COPY 2 bar
# another pair of UID STORE, UID EXPUNGE pending
S: y1 OK [COPYUID ...] done
C: y3 UID STORE 2 (+FLAGS.SILENT \Deleted)
S: y2 OK [COPYUID ...] done
C: y4 UID STORE 2 (+FLAGS.SILENT \Deleted)
S: y3 OK done
C: y5 UID EXPUNGE 2
S: y4 OK done
C: y6 UID EXPUNGE 2
S: * VANISHED 2
S: y5 OK done
S: y6 OK done

One can argue that my client could take care to never schedule more than 
one concurrent "move" operation. Yes, it could. This corner case is one 
of the motivations for UID MOVE being proposed in the first place -- so 
that clients don't have to "cope with partial failures and side 
effects", to quote the draft.

(My client will not expunge messages when UIDPLUS is not announced. I 
did not dare to temporarily remove the "other" \Deleted flags, call 
EXPUNGE and restore the \Deleted back as this process is inherently racy.)

In presence of UID MOVE extension, I would not create a 
CopyMessagesTask, but a MoveMessagesTask, and the communication would 
look like this:

C: y1 UID MOVE 2 foo
# network is slow to respond
C: y2 UID MOVE 2 bar
S: * OK [COPYUID ...] copied
S: * VANISHED 2
S: y1 OK done
S: y2 OK done

At this point, my client actually has no way to know where the message 
got copied to. That's a small regression compared to the UID COPY/UID 
STORE/UID EXPUNGE sequence.

So, a quick summary:

- There's at least one client which will happily pipeline UID MOVE. No 
other client has implemented the UID MOVE draft yet, AFAIK.

- Pipelined UID MOVE (even on non-overlapping message sets) means that 
the client cannot reasonably infer the target mailbox where the messages 
got moved to, removing the benefits of the COPYUID response.

I can live with this (in fact, to be honest with you, the cache 
implementation which I'm using now does not support reference counting, 
so it ignores COPYUID for the time being). However, as we are evaluating 
a new extension, let's take our time to make it good enough. Therefore, 
I propose that we choose one of the following results:

0) Do nothing.
1) Ban "MOVE" and "UID MOVE" pipelining due to ambiguity.
2) Ban "MOVE" pipelining due to ambiguity and add a note that "UID MOVE" 
pipelining leads to COPYUID being unusable.
3) Ban "MOVE" pipelining due to ambiguity, replace COPYUID with 
something that contains the reference to the target mailbox or the 
command's tag.

I find 3) to be the best. 2) is OK for me, 1) is bad, 0) is the worst, 
IMHO. But before choosing 0), please show me why I'm wrong.

With kind regards,
Jan

-- 
Trojita, a fast e-mail client -- http://trojita.flaska.net/

---

From: Barry Leiba <[email-masked]>
Date: Sat, 1 Sep 2012 11:29:36 -0400

> exists is only an indication that there is ample precedent in IMAP for having
> such restrictions.

Absolutely; this document is defining a new command, and it can put
whatever restrictions it likes on the use of that new command.  If the
restrictions start developing in a way that seems to violate the
"gestalt" of IMAP, participants can object and things can go in a
different direction.  Restrictions on pipelining do not seem to me to
violate the IMAP gestalt at all.

> the semantics rather obviously aren't the same.

I think this is a very important comment, and I think it leads to something:
Let me strongly suggest that this document *downplay* the COPY + STORE
+ EXPUNGE aspect, and focus on the actual result.  We're stuck in the
COPY + STORE + EXPUNGE mindset because it's the way we used to do
things, but I do NOT think it does the document or the proposed
function any favours to make a point of saying that it has to be
equivalent to that.

The *most* I would say about it is the text in the Overview that says
that COPY + STORE + EXPUNGE is the way this has been done heretofore,
and that it's the intent that this command replace that mechanism with
something having a similar effect.  I think that leaning on the COPY +
STORE + EXPUNGE model beyond that is taking things in the wrong
direction.

Specifically:

- I would re-word the second paragraph of Section 3 to talk about the
result of the command, NOT in terms of COPY + STORE + EXPUNGE.

- I would re-word the penultimate paragraph of Section 3 to put it in
terms of COPY only; I don't think it's necessary to go beyond that
here.

- I would re-word Section 4.2 to this:

   The ACL rights [RFC4314] required for the UID MOVE are the
   union of the ACL rights required for UID STORE, UID COPY and
   UID EXPUNGE.

(And you need a normative reference to 4314 (yes, you do).)

- I would re-word the first paragraph of Section 4.3 to this:

   Servers supporting UIDPLUS [RFC4315] MUST send COPYUID
   in response to a UID MOVE command.

The second paragraph also needs some re-wording.

- The second Section 4.3 needs to be renumbered to 4.4, and I would
re-word that this way:

   The QRESYNC extension [RFC5162] directs the server to send VANISHED
   rather than EXPUNGE in response to the UID EXPUNGE command. The
   same requirement applies to the UID MOVE command.

Barry, as participant

---

From: Ned Freed <[email-masked]>
Date: Sun, 02 Sep 2012 19:19:54 -0700 (PDT)

> violate the IMAP gestalt at all.

Agreed. That said, if there's a real use-case for pipelining overlapped
MOVEs and the cost of addressing the issue is low, I don't object to
following that path either.

> function any favours to make a point of saying that it has to be

I didn't intend to take it that far but now that you have I find myself liking
the approach a lot. If we need more explanation than what would result from
your changes below perhaps the right thing to do is to explain this as its own
thing first, but then relate it to COPY/STORE/EXPUNGE but emphasing the
*differences*.

> (And you need a normative reference to 4314 (yes, you do).)

On consideration I think you are correct. You can't talk about
performing an operation on something without knowing for sure what
that something is, which makes this normative.

>    same requirement applies to the UID MOVE command.

I have no objection to any of these changes.

				Ned

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Tue, 4 Sep 2012 11:59:22 +0200

On 09/01/2012 04:24 AM, Ned Freed wrote:
> First, there's nothing in the section that excludes UID commmands from its
> restriction. Such an interpretation might make sense if UID commands were
> introduced in a different document, but that's rather obviously not the
> case.

When I wrote text, I noticed that the UID MOVE status could be arguable.

"a UID MOVE 123 foo" is legal even if 123 does not exist, but if the 
client does not know whether 123 exists at the time the command is sent 
to the server, then the command could be said to be is ambiguous, and 
5.5 prohibits ambiguous commands.

IMO ambiguous means something else: It means that the server cannot 
determine exactly what to do based on its parsing of the command. By 
this reading, the command above is legal, and UID MOVE can often be 
pipelined with other commands.

Arnt

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Tue, 4 Sep 2012 22:47:24 +0200

> following that path either.

I want move to be implementable in clients like this:

   if ( move supported ) {
     uid move
   } else {
     uid copy
     uid store
     uid expunge
   }

The case for making the top branch pipelinable is that the bottom branch 
is (well, to the degree it is).

That's also why I defined move in the terms I did.

Arnt

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Tue, 4 Sep 2012 11:55:41 +0200

On 08/31/2012 11:09 PM, Timo Sirainen wrote:
> It's definitely not obvious that 5.5 applies in this case, and I wouldn't really even agree that it does apply (for MOVE yes, for UID MOVE I think not). But if it's explicitly mentioned I guess that's fine.. The other possibility would be to do it similar to ESEARCH replies and include the tag (as in Jan's suggestion, although it would need to be done differently).

With editor hat off: I disagree.

Adding another response code only helps in an odd case, and when it does 
help, all it helps with is with cache hit ratio. I'm not sure it does 
even that: How often does the user retrieve the just-moved messages, and 
how much local storage is available for caching? In this csae, and with 
editor firmly off, I think we're better off with a simpler spec than a 
larger client cache.

There is a certain tendency among us (myself included, I am sad to say) 
to solve the problems we identify, without stopping to think whether the 
additional complexity is really warranted.

Arnt

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Tue, 4 Sep 2012 22:52:07 +0200

On 09/01/2012 04:24 AM, Ned Freed wrote:
> sequence were identical to MOVE, there would be no need for MOVE.

As I understand it, MOVE exists mostly to stop complaints about having 
to handle errors part-way through. If a three-command sequence could be 
made to have the semantics and capabilities of a single command, IMAP 
would be such a different protocols that it might also cook breakfast 
for you.

Arnt

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Tue, 4 Sep 2012 23:15:54 +0200

On 09/01/2012 05:29 PM, Barry Leiba wrote:
> Let me strongly suggest that this document*downplay*  the COPY + STORE
> + EXPUNGE aspect, and focus on the actual result.
...
> We're stuck in the
> things,

Uh, I wrote it that was explicitly because I want MOVE to be a slot-in 
replacement in existing client code and want emphasize its equivalence. 
Do you think this is a valuable property?

> result of the command, NOT in terms of COPY + STORE + EXPUNGE.

Doable, I suppose, but I have a feeling that either the document 
emphasizes the result and leaves readers to infer the equivalence, or it 
emphasizes the equivalence and leaves readers to infer the result. I 
know what I prefer, but my preference is that of a random WG 
participant. The editor will bow to majority opinion.

> terms of COPY only; I don't think it's necessary to go beyond that

I rewrote entirely. It was a rotten paragraph.

> - I would re-word Section 4.2 to this:

In section 4, you suggest using simpler sentences than I wrote, but 
occasionally they sound normative. Would you (as AD) prefer simpler 
sentences with normative language over ones that clearly only point out 
what the rules in other RFC are?

> (And you need a normative reference to 4314 (yes, you do).)

I made the reference normative. I don't see why though, could you explain?

>     in response to a UID MOVE command.

In this case you even suggest an upper-case MUST. Do you think section 4 
ought to become normative?

>     same requirement applies to the UID MOVE command.

OK.

Arnt

---

From: Jan Kundrát <[email-masked]>
Date: Wed, 05 Sep 2012 11:34:52 +0200

> editor firmly off, I think we're better off with a simpler spec than a

The whole point of the COPYUID is to help with the cache hit ratio. If 
that was not a goal worth making some work, there would be no reason for 
UIDPLUS' COPYUID to exist.

We are already making a change in the COPYUID's semantics by moving it 
from a tagged response to an untagged one. This change brings along a 
loss of information; data which were previously implicitly available by 
the virtue of the tagged response are now missing. If the client wants 
to use the COPYUID response in its intended way anyway, it will have to 
determine the missing data somehow. What I claim here is that this has a 
significant cost in clients which use asynchronous dispatch of commands.

Unfortunately, it is not possible to both "implement UID MOVE" and 
"reuse COPYUID as-is" at the same time; we have established that earlier 
and this observation has led to the proposed untagged COPYUID. However, 
this fact alone means that the new form of COPYUID is different from the 
previous one (in UID COPY). We cannot assume that the existing clients 
will be able to process untagged COPYUID.

> additional complexity is really warranted.

This would be an excellent point if the draft used COPYUID as-is. 
However, the proposed way is different than in basic UIDPLUS, so the 
change to accommodate a former problem has been made already. Why not 
make a second change to fix another issue which was identified early 
enough in the process?

Yes, it has a cost. Is there any other client developer willing to 
implement UID MOVE here who might tell us which variant of the 
COPYUID/MOVEUID they would prefer to implement in their clients?

With kind regards,
Jan

---

From: Barry Leiba <[email-masked]>
Date: Wed, 5 Sep 2012 09:04:50 -0400

> replacement in existing client code and want emphasize its equivalence. Do
> you think this is a valuable property?

I think what's valuable in a protocol spec is to say what has to
happen in the protocol.  What has to happen is some variant of "the
message appears in the target mailbox with a new UID, and disappears
from the source mailbox, in what the client perceives as an atomic
operation."

Then I think it's perfectly fine to say, as an informational note,
that this is approximately equivalent to COPY + STORE + EXPUNGE, and
that clients that are currently using a sequence like that to perform
this function can switch to MOVE seamlessly, or whatever you want to
say about it in that regard.  That's what I mean by "downplay" (or
"play down", if you prefer): I'm not talking about being "silent"
about it, but not stressing, all over the document, that MOVE is
*defined as* COPY + STORE + EXPUNGE.  We only need to give
non-normative implementation advice on this, and probably only once.

But it's important that the normative specification of the protocol
NOT specify implementation details.

> I rewrote entirely. It was a rotten paragraph.

It happens, even in the best of families.

> sentences with normative language over ones that clearly only point out what
> the rules in other RFC are?

You know that we disagree on this, you and I; we should have the
working group weigh in:
I think that when you talk about how implementations of <extension E>
handle MOVE, you have to be normative.  You can't say, for instance,
that UIDPLUS implementations kinda-sorta-might-consider sending
COPYUID -- if you expect COPYUID here, you have to make it a normative
requirement that UIDPLUS implementations do this when they add support
for MOVE.  If you expect ACL implementations to do the right thing for
MOVE with respect to which access controls they require, you have to
make it normative.

That's also why the UIDPLUS and ACL references have to be normative
references: you're putting normative requirements on implementations
of those specs when they choose to add MOVE support.

> ought to become normative?

I'll add to the above that specification language doesn't HAVE to say
"MUST" in order to be normative.  In the case of my suggestions, I
think 2119 language is right for those spots.  But there's lots of
normative language in the spec that doesn't use 2119 words, too.

Barry

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Tue, 4 Sep 2012 10:52:48 +0200

5.5 is a botch. This sentence specifies what happens in the situation 
Jan describes (where the client unknowingly sends ambiguous commands):

    If the server detects a possible ambiguity, it MUST execute commands
    to completion in the order given by the client.

I take that as a misleading way of saying "the server may do whatever 
comes easiest, so long as it only executes commands, and doesn't 
actually contain code to detect ambiguities".

But I agree with Ned: It would be good for the document to talk more 
about this. I didn't so far, because I don't want to write anything that 
could sound like a rule and be read to conflict with existing rules.

I'm going through the document now and trying to fix these problems. 
I'll send this reply (well, when the plane lands) and only reply to 
other messages in the thread if anything warrants particular comment.

Sorry about the late replies. Travel and more travel.

Arnt

---

From: Ned Freed <[email-masked]>
Date: Sat, 08 Sep 2012 09:50:46 -0700 (PDT)

>      uid expunge

I think that's a fine goal, but the thing this sort of presentation ignores
is response handling. Sure, you can get the same effect with the two
sequences in most cases, but when something goes wonky the handling in the
latter case is potentially a lot more difficult.

Again, if there's no advantage to using MOVE there's no point in specifying it. 
And the advantage that accrues just from sending one versus three commands
is insignificant IMO.

And since there has to be an advantage for a specification to be useful, that
then means it's possible this may result in clients that require MOVE. That's
the balancing act involved any time we specify an extension to anything.

> is (well, to the degree it is).

Which I guess is an argument for making changes to disambiguify the overlapped
pipelining case. Or not - remember we're talking about overlapped pipelining,
not pipelining in general.

				Ned

---

From: Ned Freed <[email-masked]>
Date: Sat, 08 Sep 2012 09:57:22 -0700 (PDT)

> would be such a different protocols that it might also cook breakfast

I'm for that - I could use a good breakfast right now ;-)

				Ned

---

From: Bron Gondwana <[email-masked]>
Date: Sat, 08 Sep 2012 19:45:12 +0200

> And the advantage that accrues just from sending one versus three commands

The massive advantage we've already seen is that a "MOVE" can be performed
while the user is over quota, whereas COPY/STORE/EXPUNGE can't without the
server delaying the quota check until some theoretically later point.

Besides, a client with even the slightest sense can't pipeline
COPY/STORE/EXPUNGE.  You'd have to be totally insane.  The above
"over quota on copy" case leads to you deleting the only copy of
your messages if you pipelined all three commands.

Bron.
-- 
  Bron Gondwana
  [email-masked]

---

From: Jan Kundrát <[email-masked]>
Date: Sat, 08 Sep 2012 19:45:20 +0200

> not pipelining in general.

Actually there's still a problem when pipelining non-overlapping ranges 
which move to different mailboxes. Clients have to explicitly look up 
the untagged COPYUID to the respective UID MOVE command, which is 
suboptimal in my opinion.

Assuming the servers are "reasonable" and return only those UIDs which 
were referenced in the UID MOVE command (which is something not mandated 
by either 4315, or by the current draft, AFAIK), the clients would work 
well enough with something like this:

void handle_untagged_COPYUID(source_UIDs, ...):
   for each command in pending_commands if command.type == UID_MOVE:
     if (command.uid_range.contains(any_of(source_UIDs))):
       command.handle_COPYUID(source_UIDs, ...)

Please note that a simple-minded check like "if (command.uid_range[0] == 
source_UIDs[0])" will fail when the first message fails to get copied 
(which is always possible when it got expunged from a concurrent session).

The algorithm would also be much worse if servers were allowed to return 
UIDs which weren't requested by the corresponding UID MOVE. Could the 
draft clarify that this is forbidden?

(An observation: if the COPYUID contained an explicit mailbox reference, 
servers would be able to send these to other concurrent sessions as 
well, for all of COPY/UID COPY/MOVE/UID MOVE commands. That's clearly 
outside the scope of this draft, very likely too late to be introduced 
now and -- I suspect -- it would also bring very negligible benefit in 
the real world (clients being disconnected etc), much smaller than the 
unofficial DIGEST proposals, but I still wanted to mention this. Just a 
random observation.)

With kind regards,
Jan

---

From: Ned Freed <[email-masked]>
Date: Sat, 08 Sep 2012 11:01:30 -0700 (PDT)

> your messages if you pipelined all three commands.

*Very* good point, thanks for making it.

				Ned

---

From: Jan Kundrát <[email-masked]>
Date: Sat, 08 Sep 2012 20:17:59 +0200

> *Very* good point, thanks for making it.

To prevent a possible misunderstanding -- while it is indeed insane to 
pipeline COPY/STORE/EXPUNGE *and* equally insane to pipeline their UID 
variants, there's no risk of data loss when pipelining the UID STORE and 
UID EXPUNGE tuple.

It is also completely safe to pipeline independent "move operations", 
i.e. one does not have to wait for all three to finish before invoking 
the next UID COPY. These run in parallel just fine.

I assume that all participants in this discussion are well aware of 
these facts, but I'd like to make this situation clear for other readers 
who might mistakenly interpret this subthread as "you cannot pipeline 
moves anyway, so what's the point?".

Cheers,
Jan

---

From: Ned Freed <[email-masked]>
Date: Sat, 08 Sep 2012 11:09:04 -0700 (PDT)

>        command.handle_COPYUID(source_UIDs, ...)

In other words, there's a reasonable way to handle it as long as nothing
bizarre happens.

> draft clarify that this is forbidden?

It had never occurred to me to imagine a case where a UID that wasn't
specifically requested could be returned. I have trouble believing a server
would do that, but if you really believe it could happen I don't have
a problem with explicitly prohibiting it.

That said, this sort of thing is in general a slippery slope. Specifications
that attempt to expliitly outlaw every possible form of stupidity end up being
unreadable and useless. (And yes, it's been tried, e.g. GOSIP.)

				Ned

---

From: Bron Gondwana <[email-masked]>
Date: Sun, 09 Sep 2012 20:49:32 +0200

> unreadable and useless. (And yes, it's been tried, e.g. GOSIP.)

My turn to say "an excellent point, thanks for making it"!

I think Jan does have a point, that if your client is aggressively filing a pile
of MOVE commands up the wire, it has to know what semantics to expect.

If they are overlapping MOVE commands, I would argue that the client is plain
wrong to be doing it an expecting a consistent result.  It should block further
changes being made to the UI element associated with the source UID until the
server response has been received.

If they're not overlapping, then the resulting COPYUID responses should be quite
easily matchable to their sources.

Even in the non-UID varient - you presumably know the UIDs before you sent the
request, or any COPYUID, no matter how well annotated, will be useless for cache
management.

Yes, it's a bit of bookkeeping on the client side.  You need to annotate each
source UID with the destination folder - then when the associated COPYUID comes
back, you can match them up.  That annotation will also be handy for knowing
that the message is "in transit", so you can't try moving it again!

Bron.
-- 
  Bron Gondwana
  [email-masked]