Mailing-List: contact dev-help@subversion.apache.org; run by ezmlm
Precedence: bulk
Received-SPF: error (athena.apache.org: local policy)
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
  s=s1024; d=btopenworld.com;
  h=X-YMail-OSG:Received:X-Rocket-MIMEInfo:X-Mailer:References:Message-ID:Date:From:Reply-To:Subject:To:MIME-Version:Content-Type:Content-Transfer-Encoding;
  b=EzHVGahx1J7PHtAtV/ZjWyiz9ZrFhyK6756PxpW0Lfb1wGxm5uvKsP6pvLtQR+zTy/szQZGPUUnVCLuPXyHO1MObVIlVTQje5E8h1j+/fQauMiSMFZzVE7D0KlcZ1Z7HaYznfSlIqdlyWpS2Ryby2va1FMAM1APVjUMkWpTM4Eo=;
References: 
Message-ID: <1372087321.76009.YahooMailNeo@web186101.mail.ir2.yahoo.com>
Date: Mon, 24 Jun 2013 16:22:01 +0100 (BST)
From: Julian Foad <julianfoad@btopenworld.com>
Reply-To: Julian Foad <julianfoad@btopenworld.com>
Subject: Ev2 as a move-aware editor
To: "dev@subversion.apache.org" <dev@subversion.apache.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable

For move tracking we need a move-aware editor.=A0 svn_editor_t ("Ev2") is d=
esigned to support moves.=A0 However, I'm not clear how its move support is=
 meant to work, on a fairly basic level:=0A=0A=A0 * What are the ordering r=
ules for moves?=0A=0A=A0 * Are the move operations to be interprested in se=
ries or in parallel?=0A=0A=A0 * When an operation refers to a node that is =
involved in a move, how are the paths to be interpreted?=0A=0AFrom conversa=
tions with other devs I know I'm not the only one.=A0 There are a number of=
 rules written down in <svn_editor.h> but to my reading they didn't seem to=
 explain the overall scheme, and they contain inconsistencies, some of whic=
h I have posted as queries to this list in the past but remain unresolved [=
1].=0A=0AHaving failed to grok what is intended, I have deliberately put of=
f trying to dig further into Ev2's version of move support, until now, in o=
rder to think freely about the theory and to focus more evenly on all the a=
reas of move tracking.=A0 (That's why I started using Ev1 in my experimenta=
l branch [2] and in my notes [3].)=A0 But now we should tackle this.=0A=0AS=
o, please could somebody help to elucidate how Ev2 move support works or sh=
ould work?=0A=0A=0A=3D=3D Basic Theory =3D=3D=0A=0AI can imagine two possib=
le extremes for the overall mode of operation to which such an editor *coul=
d* be designed: parallel and sequential.=A0 I'll mention some essential cha=
racteristics of each.=0A=0A=3D=3D Sequential =3D=3D=0A=0AEdits are describe=
d sequentially, incrementally.=A0 The consumer maintains a state that descr=
ibes the 'current' tree shape, starting with the initialtree shape, and bei=
ng changed incrementally by each edit operation.=0A=0AEach edit operation r=
efers to paths that exist in the 'current' tree state and/or that will exis=
t in the next state.=0A=0A=3D=3D Parallel =3D=3D=0A=0AThe producer sends al=
l changes in parallel or in an unspecified order.=A0 Each change is describ=
ed independently of all other changes: it refers to paths (or nodes) in a w=
ay that doesn't depend on the other changes being sent.=A0 In fact, rather =
than talking about 'operations' or 'changes', the semantics required here i=
s to describe the final state in any compact way, not necessarily in terms =
of changes against the initial state.=0A=0A(One case that may seem difficul=
t to parallelize is adding a new parent directory and its children.=A0 How =
can the consumer accept a child node before the creation of the parent dire=
ctory?=A0 The answer is simply that the consumer would be designed to opera=
te this way, storing the children either in their final form or in a tempor=
ary form, and linking them into the parent once all necessary information h=
as been received.)=0A=0A=3D=3D Hybrid =3D=3D=0A=0AWe could mix these and ha=
ve a scheme that is partly parallel, partly sequential, according to some a=
dditional rules.=A0 That is fine, but more complex to describe and understa=
nd.=0A=0ANote that while Ev1 is mostly sequential, the copy-from field of a=
 copy (when used for a move) is more like the parallel scheme, since it ref=
ers to a path in the initial tree state and not a path in the current tree =
state.=0A=0A=3D=3D Cyclic moves =3D=3D=0A=0AWe need to accommodate arbitrar=
y sets of moves, including cycles.=A0 For an example, we'll use a simple cy=
cle, swapping two siblings A and B.=A0 This ability is needed for two reaso=
ns:=0A=0A=A0 * Ev1 supports this (del A, copy A from B@OLD, del B, copy B f=
rom A@OLD).=0A=0A=A0 * A single edit must be able to represent the combinat=
ion of any series of edits, and a series of moves can result in a cycle eve=
n if each individual edit only supports non-cyclic moves.=A0 (1: mv B C.=A0=
 2: mv A B.=A0 3: mv C A.)=0A=0AIn a parallel scheme, no special treatment =
is necessary:=0A=0A=A0=A0=A0 A -> B=0A=A0=A0=A0 B -> A=0A=0AIn a sequential=
 scheme, there are two ways to accommodate cyclic moves:=0A=0A=A0 * Allow m=
oving to a temporary path and then later to the final path:=0A=A0=A0=A0 mv =
A tmp; mv B A; mv tmp B=0A=0A=A0 * Allow a 'swap A B' or 'rotate A B ...' o=
peration:=0A=A0=A0=A0 rotate A B=0A=0A=3D=3D Swap or Rotate =3D=3D=0A=0Aswa=
p(A,B) =3D=3D { A->B || B->A }=0A=0Ais a primitive operation.=A0 ('||' indi=
cates 'in parallel'.)=0A=0Arotate(A,B,...N) =3D=3D { A->B || B->... || ...-=
>N || N->A }=0A=0Ais non-primitive, since any rotate can be composed from m=
ultiple sequential swaps.=A0 For example, rotate(A,B,C) =3D=3D { swap(B,C);=
 swap(A,B) }.=A0 It is no more useful to rotate more than two paths in one =
operation (rotate(A,B,C)) than to move more than two paths=A0 in one operat=
ion (move(A,B,C) =3D=3D { A->B || B->C }).=0A=0ASo if we have a sequential =
scheme and we don't want to use temporary paths, we should include the 'swa=
p' primitive rather than a 'rotate'.=0A=0A=0A=3D=3D Ev2 =3D=3D=0A=0AOne of =
Ev2's goals is to parallelize text modifications, in order to take advantag=
e of Serf's parallelism.=A0 What about tree changes, and specifically what =
are the semantics of the 'move' operation?=A0 The Ev2 documentation indicat=
es sequential requirements for the 'add' operation (parent before children)=
, and also in this rule:=0A=0A=A0* - The ancestor of an added, copied-here,=
 moved-here, rotated, or=0A=A0*=A0=A0 modified node may not be deleted. The=
 ancestor may not be moved=0A=A0*=A0=A0 (instead: perform the move, *then* =
the edits).=0A=0AThe doc string for 'svn_editor_move' says:=0A=0A=A0* Move =
the node at @a src_relpath to @a dst_relpath.=0A=A0*=0A=A0* @a src_revision=
 specifies the revision at which the receiver should=0A=A0* expect to find =
this node.=A0 That is, @a src_relpath at the start of=0A=A0* the whole edit=
 and @a src_relpath at @a src_revision must lie within=0A=A0* the same node=
-rev (aka history-segment).=A0 This is just like the=0A=A0* revisions speci=
fied to svn_editor_delete() and svn_editor_rotate().=0A=A0* ...=0A=0AThe di=
scussion implies that "the node at src_relpath" refers to a node in the ini=
tial tree state.=A0 In that respect, it's a parallel operation: the source =
reference doesn't depend on previous moves.=A0 But look at the 'move_cb' im=
plementation in libsvn_fs/editor.c:=0A=0A=A0 # src_root =3D=3D *initial* tr=
ee state=0A=0A=A0 svn_fs_copy(src_root, src_fspath, root, dst_fspath, scrat=
ch_pool)=0A=A0 /* Notice: we're deleting the src repos path from the dst ro=
ot. */=0A=A0 # root =3D=3D *current* tree state (txn)=0A=A0 svn_fs_delete(r=
oot, src_fspath, scratch_pool)=0A=0AThe delete of src_relpath within the cu=
rrent tree state is potentially at odds with the copy from src_relpath rela=
tive to the initial state.=A0 The delete would delete the wrong thing if th=
e original node at this path has already been replaced, or would try to del=
ete a non-existent node if it had already been deleted or moved away.=A0 Co=
uld it have been replaced or deleted or moved away, if not itself then perh=
aps by a copy/move/add/delete of a parent directory?=0A=0ALet's try the fol=
lowing scenario:=0A=0A=A0 A->A2 || A/B->B2=A0 # move a child of a moved par=
ent=0A=0ATry with Ev2:=0A=0A=A0 move(src_relpath=3D'A', src_rev=3D100, dst_=
relpath=3D'A2', replaces_rev=3D-1)=0A=A0 move(src_relpath=3D'A/B', src_rev=
=3D100, dst_relpath=3D'B2', replaces_rev=3D-1)=0A=0AThe implementation show=
n above would fail in the second move when trying to delete 'A/B', because =
that path no longer exists in the transaction after the first move deleted =
the whole subtree at 'A'.=0A=0AThe other way works fine:=0A=0A=A0 move(src_=
relpath=3D'A/B', src_rev=3D100, dst_relpath=3D'B2', replaces_rev=3D-1)=0A=
=A0 move(src_relpath=3D'A', src_rev=3D100, dst_relpath=3D'A2', replaces_rev=
=3D-1)=0A=0ASo these moves are not parallelizable with this implementation.=
=A0 (Is that implementation wrong?)=0A=0AEv2 also documents (as the first D=
riving Order Restriction) that there must be an alter_directory call for th=
e parent of moved-away node 'A/B'.=A0 What does this look like?=0A=0A=A0 al=
ter_dir('A', ...)=0A=0Aor=0A=0A=A0 alter_dir('A2', ...)=0A=0A?=A0 Can the a=
lter_dir come before or after the move of 'A' to 'A2'?=A0 Is the path it re=
ferences 'A' in either case, or 'A2' in either case, or 'A' if it comes bef=
ore the move and 'A2' if it comes after the move?=0A=0ACan we start with a =
clear consensus of whether we're trying to deliver a sequential or a parall=
el editor?=0A=0A=0A- Julian=0A=0A=0A[1] For example, email subject "Re: Ev2=
 -- Driving Order Restrictions" from Julian Foad on 2012-07-18, <http://svn=
.haxx.se/dev/archive-2012-07/0247.shtml>.=0A=0A[2] 'move-tracking-1' branch=
, <http://svn.apache.org/repos/asf/subversion/branches/move-tracking-1/>.=
=0A=0A[3] Wiki page 'MoveDev/MoveDev', <https://wiki.apache.org/subversion/=
MoveDev/MoveDev>.=0A=0A--=0AJoin WANdisco's free daily demo sessions on Sca=
ling Subversion for the Enterprise=0A<http://www.wandisco.com/training/webi=
nars>