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

From: Jan Kundrát <[email-masked]>
Date: Fri, 31 Aug 2012 17:09:17 +0200

Hi Arnt et all,
sorry for not responding before the WGLC.

There's a problem with reusing the COPYUID in untagged responses. 
Consider the following example where a client uses pipelining for the 
UID MOVE command and moves two distinct sets of messages into two 
different mailboxes:

C: a UID MOVE 42 foo
C: b UID MOVE 66 bar
S: * OK [COPYUID 123 42 123]
S: * OK [COPYUID 456 66 10]
S: * VANISHED 42,66
S: a OK completed
S: b OK completed

In this particular example, a client could probably keep track of the 
issued UID MOVE commands, map the "COPYUID ... 42" into mailbox "foo" 
and "COPYUID ... 66" into mailbox "bar". That would still require quite 
some amount of work. Please note that the same problem does not affect 
the COPY/UID COPY commands because the COPYUID is embedded in the tagged 
OK for these commands.

And to prevent speculations -- yes, my client will happily issue 
pipelined UID MOVE when the user moves her mouse fast enough. When 
working over a slow network, one can imagine a case where there *could* 
be two such commands pipelined. My code can actually handle this 
situation reasonably well; the COPYUID is going to be processed by an 
object which remembers the UID of the messages being moved, so it's easy 
to see whether "this" COPYUID is for "this" UID MOVE or whether one 
should defer it to another one. However, reusing COPYUID in an untagged 
response leads to interesting effects when the set of UIDs of two 
pipelined commands overlaps and there are some failures.

Please note that as a result of the UID MOVE being defined in terms of 
(UID COPY, UID STORE, UID EXPUNGE), it is actually OK to attempt to UID 
MOVE an overlapping set of messages in two pipelined commands. The 
result is timing and ACL-dependant, but the sequence itself is allowed. 
Consider the following:

C: a UID MOVE 1:2 aaa
C: b UID MOVE 2:3 bbb
S: * OK [COPYUID 123 2 123] // for the "a" command moving into "aaa"
S: * OK [COPYUID 456 2 123] // for the "b" command moving into "bbb"
S: * VANISHED 1:3
S: a OK blah
S: b OK blah

In this (quite contrived, I admit) case, the commands failed to move any 
message with UID different from 2, but at the same time, messages with 
UIDs 1 and 3 are both expunged, maybe by a parallel session. The IMAP 
server for some reason decided to defer sending the EXPUNGE/VANISHED for 
these until the COPYUID got sent. The client code has no way to tell 
what happened, and a naive implementation might also try to invalidate 
its cached copy of mailbox aaa's state (or bbb's state, or both) by 
observing that the UDIVALIDITY of the target mailbox has changed.

My opinion is that the draft should be changed to use a new response 
code (like MOVEUID) which would work like this:

C: a UID MOVE 1:2 aaa
C: b UID MOVE 2:3 bbb
S: * OK [MOVEUID a 123 2 123] // for the "a" command moving into "aaa"
S: * OK [MOVEUID a 456 2 123] // for the "b" command moving into "bbb"
S: * VANISHED 1:3
S: a OK blah
S: b OK blah

If this gets changed, section 4.3 will need a rewrite.

In addition, I have troubles understanding section 4.1: "This may be 
user-visible, but should not be MUA-visible.". I haven't read the QUOTA 
RFC carefuly, though, so I might be missing something.

With kind regards,
Jan

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

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Fri, 31 Aug 2012 21:14:41 +0200

Show me a case where this is a  problem?

As far as i can understand, if uid 2 I'd moved to aaa, it cannot subsequently be moved to bbb, because it is not there to be referenced anymore. This works even for concurrent commands, because the server moves each message atomically, so one command has to be the first to move each particular message.

If you issue two moves for overlapping sets, you will get disjoint copyuid responses.

If the second command uses msns this could be a problem, I suppose.

Arnt

---

From: Dan Karp <[email-masked]>
Date: Fri, 31 Aug 2012 12:21:18 -0700 (PDT)

> If the second command uses msns this could be a problem, I suppose.

As far as I understand it, two overlapping MOVEs are not allowed by the
ambiguity rules of RFC 3501 section 5.5 (Multiple Commands in Progress).

- Dan

---

From: Jan Kundrát <[email-masked]>
Date: Fri, 31 Aug 2012 21:53:19 +0200

On 08/31/12 21:14, Arnt Gulbrandsen wrote:
> As far as i can understand, if uid 2 I'd moved to aaa, it cannot
> subsequently be moved to bbb, because it is not there to be
> referenced anymore.

The problem is that if two UID MOVE are started in parallel, there's no 
guarantee that the server will actually fully process the first one 
before the second one, and therefore clients have no idea which one has 
won. Consider the following:

C: a UID MOVE 1 aaa
C: b UID MOVE 1 bbb
S: * OK [COPYUID 123 1 1]
S: * VANISHED 1
S: a OK completed
S: b OK completed

Where's the message now, in aaa, or in bbb?

> This works even for concurrent commands, because the server moves
> each message atomically, so one command has to be the first to move
> each particular message.

My understanding of the draft's wording is that there's only a SHOULD on 
the atomicity -- i.e. it is allowed for servers to actually copy the 
message into both mailboxes before it gets expunged from the source one. 
This interpretation is somehow confirmed by the UID MOVE's definition 
which relies on UID COPY/UID STORE/UID EXPUNGE; there's nothing saying 
that this sequence should/must be atomic (and probably for a good reason).

The draft also contains a section called Open Issues (which should both 
be addressed, IMHO) -- the atomicity explanation might confirm or reject 
my claim that a message can actually be copied into two mailboxes.

With kind regards,
Jan

---

From: Ned Freed <[email-masked]>
Date: Fri, 31 Aug 2012 13:52:39 -0700 (PDT)

> ambiguity rules of RFC 3501 section 5.5 (Multiple Commands in Progress).

I agree. It's clear that streaming two moves of the same messge can produce
ambiguous results, so by section 5.5 rules it is not allowed.

That said, I think the draft needs to state this explicitly rather than relying
on everyone's full and deep understanding of all the nuances of IMAP command
semantics.

I note in passing that section 5.5 does exactly this for some less
than obvious ambiguous cases.

				Ned

---

From: Timo Sirainen <[email-masked]>
Date: Sat, 1 Sep 2012 00:09:45 +0300

> than obvious ambiguous cases.

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).

---

From: Jan Kundrát <[email-masked]>
Date: Fri, 31 Aug 2012 23:54:30 +0200

> ambiguous results, so by section 5.5 rules it is not allowed.

You are right that one can interpret that section to mean roughly "if 
any future extension defines something which can be used in an ambiguous 
way, clients cannot use that". The problem is that this restriction has 
only been ever used to restrict commands using sequence numbers and not 
those which operate on and return just the UIDs, AFAIK. So you might be 
right, but it's a stretch of an old rule, in my opinion. I would find it 
surprising that this rule would ever apply to UID MOVE, and this 
observation is supported by UID MOVE's definition in terms of (UID COPY, 
UID STORE and UID EXPUNGE) which are fine with being pipelined in the 
manner I've shown in my earlier e-mails. If this definition holds, I 
believe that 5.5 cannot apply to UID MOVE.

So let's decide whether we want to allow for pipelined UID MOVE at all. 
If that is going to be allowed, let's use this opportunity to make the 
extension as easy to implement -- for both servers and clients -- as 
possible.

What's the cost of adding a MOVEUID referring either to the command tag 
or the target mailbox?

In the current version of the draft, clients would have to do roughly 
the following if pipelined UID MOVE is allowed:

def handle_untagged_COPYUID:
   for each UID_MOVE_command in active_commands:
     for each uid in COPYUID.source_UIDs:
       if uid in UID_MOVE_command.source_UIDs:
         # now we're sure that it is our command
         process_copyuid_here() # processes all UIDs in the COPYUID
         return
   # definitely not our command, do nothing

It is doable, but it's very non-obvious that such a convoluted handling 
is in fact required to catch all the corner cases (like some messages 
failing to move). It is also an O(n^2) in the worst case compared to 
O(1) with a MOVEUID variant which refers to a mailbox/command.

With kind regards,
Jan

---

From: Ned Freed <[email-masked]>
Date: Fri, 31 Aug 2012 19:24:35 -0700 (PDT)

> those which operate on and return just the UIDs, AFAIK.

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.

Second, the reason such considerations may not apply to UID commands is because
those commands have different semantics that eliminate such concerns.

> So you might be
> right, but it's a stretch of an old rule, in my opinion.

Absent a much more compelling argument than has been given so far I reject the
notion that this is any sort of stretch. That would be true even if there isn't
a single case where this restriction has applied to a UID-based command.

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.

> I would find it

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.

> So let's decide whether we want to allow for pipelined UID MOVE at all.

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.

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.

> What's the cost of adding a MOVEUID referring either to the command tag

Benefits first. Then costs.

> O(1) with a MOVEUID variant which refers to a mailbox/command.

All this assumes that a client would actually want to do it.

				Ned