Version control systems allow a group of people to work together on a set of documents over a network by merging their changes into the same source repository. The existing version control systems o®er limited support concerning con°ict resolution and tracking of user activity. In this paper we propose a customisable operational transformation merging approach for hierarchical documents that o®ers the possibility to specify and resolve the con°icts at di®erent granularity levels. Our proposed approach also achieves better e±ciency compared to existing approaches for merging documents with linear structures.
Asynchronous collaborative editing systems have been developed to support a group of people editing a document collaboratively over a network by allowing the users to modify in isolation the copies of the document and afterwards synchronise their copies in order to reestablish a common view of the data.
Well known versioning systems such as CVS [
The FORCE [
In this paper we propose a customisable operation-based merging algorithm that works on a hierarchical representation of documents, allowing the possibility of de¯ning and resolving the con°icts by using di®erent semantic units corresponding to the document levels. An important advantage of our algorithm based on the tree representation is its improved e±ciency compared to other merging approaches that use a linear representation of the documents. Our merging algorithm recursively applies over the di®erent document levels any existing merging algorithm relying on the linear structure of the document.
The paper is structured as follows. In the next section we present an existing linear based merge algorithm that has been used by our tree-based merging algorithm recursively over the document levels. We describe our tree-based approach in Section 3. In Section 4 we compare our approach with some related work. Concluding remarks are presented in the last section. 2
In this section we are going to brie°y introduce the operational transformation mechanism and the way this mechanism has been applied for linear-based merging approaches.
The basic operations supplied by a con¯guration management tool are checkout, commit and update. A checkout operation creates a local working copy of the document from the repository. A commit operation creates in the repository a new version of the document based on the local copy of the document, given that the repository does not contain a more recent version of the document to be committed than the local copy. An update operation performs the merging of the local copy of the document with the last version of that document stored in the repository.
In order to explain the basic operational transformation approach [
In what follows we are going to brie°y describe the merging algorithms
applied for the linear representation of documents as implemented in [
In the commit phase, the repository simply executes sequentially the operations performed in the local workspace. In the checkout phase the local workspace is emptied and all the operations from the repository representing the delta between the version of the document the user wants to work on and the initial version of the document are executed into the local workspace of the user.
In the updating phase, the merging algorithm has to be performed between the list of operations executed in the local workspace LL and the list of operations DL representing the delta between the most recent version from the repository and the version the local user started working on. Two basic steps have to be performed. The ¯rst step consists of transforming the remote operations from DL in order to include the e®ect of the local operations. The second step consists of transforming the operations in LL in order to include the e®ects of the operations in DL, the list of the transformed local operations representing the new delta into the repository. In the case that operation Oi belonging to DL is in con°ict with an operation from LL, Oi cannot be executed in the local workspace and it needs to be included into the delta as its inverse in order to cancel the e®ect of Oi. Moreover, all operations following it in the list DL need to exclude its e®ect. 3
In this section we are going to present a generalisation of the previously described linear-based merging algorithm, that works for a hierarchical structure of the document.
We model the text document as consisting of the following levels of granularity: document, paragraph, sentence, word and character, document being the highest granularity level and character being the lowest granularity level.
Each workspace stores locally a copy of the hierarchical structure of the document. Each node (excluding leaf nodes) will keep a history of insertion or deletion operations associated with its children nodes. The structure of the document is illustrated in Figure 1.
Levels Hiasttoprayrafgorraopphelreavtieolns
Document Doc. Hist.
Paragraph Pa 1 Pa1 Hist. Pa 2 Pa2 Hist.
Pa 3 Pa3 Hist.
History for operations on sentences in paragraph Pa3 Document Sentence Word Character …
Se 3.1 Se3.1 Hist.
Se 3.2 Se3.2 Hist.
W 3.1.1 W3.1.1 Hist. W 3.1.2 W3.1.2 Hist. books, the hierarchical structure consisting of chapters, sections, paragraphs, sentences, words and characters or on XML documents.
The commit and checkout phase follow the same principles as described for the linear representation of the documents, with the addition that, in the commit phase, the hierarchical representation of the history of the document is linearised by using a breadth-¯rst traversal of the tree. In this way, the ¯rst operations in the log will be the ones belonging to the paragraph logs, followed by the operations belonging to the sentence logs and ¯nally the operations belonging to the word logs.
The update procedure achieves the actual update of the local version of the hierarchical document with the changes that have been committed by other users to the repository and kept in a linear order into the remote log. The merging procedure has as objective the computing of a new delta to be saved in the repository, i.e. the replacement of the local log associated with each node with a new one which includes the e®ects of all non con°icting operations from the remote log and the execution of a modi¯ed version of the remote log on the local version of the document in order to update it to the version on the repository.
The update procedure is repeatedly applied for each level of the document starting from the document level. The ¯rst step of the merging algorithm consists in the selection of the remote level log containing those operations from the remote log that have the level identical with the level of the operations from the history bu®er of the current node. The operations belonging to the remote level log are eliminated from the remote log. Since some nodes of the tree might get deleted or inserted during the update process applied for the previous upper levels of the document, the operations in the local log of the current node need to adapt their positions to correspond to the current position in the tree. Afterwards, the basic merging procedure for linear structures is applied to merge the local log of the current node with the remote level log. As a result of the merging procedure, the new remote log representing the operations that need to be applied on the local document and the new local log representing the operations to be saved on the repository are computed. After the new remote log is applied locally, the operations from the remote log are transformed against the operations in the local log and are divided among the children of the current node. Afterwards, the merging procedure is recursively called for each child.
As in the case of the real-time collaborative text editing [
In what follows we will illustrate the asynchronous communication by means of an example. Consider that the repository contains as version V0 the document consisting of only one paragraph with one sentence: \Absence increase great loves." Further suppose a con°ict is de¯ned between two operations concurrently inserting a character in the same position of the word and the policy of merging is that, in the case of con°ict, local modi¯cations are kept automatically. Further, assume two users check out version V0 from the repository into their private workspaces. The ¯rst user performs the operations O11=InsertChar(\d",1,1,2,9) of inserting the character \d" in the ¯rst paragraph, ¯rst sentence, second word as the last character and O12 = InsertW ord(\the"; 1; 1; 3) in order to obtain the version \Absence increased the great loves." The second user performs the operation O21, O21 =InsertSentence(\And diminishes small ones.",1,2) and O22 =InsertChar(\s",1,1,2,9) in order to obtain \Absence increases great loves. And diminishes small ones." Suppose that both users try to commit, but U ser1 gets access to the repository ¯rst, while U ser2's request will be queued. After the commit operation of U ser1, the last version in the repository will be V1 =\Absence increased the great loves." The di®erence between V1 and V0 in the repository DL10 = [O12; O11] is obtained as a result of the linearisation of the history bu®er distributed throughout the tree.
When U ser2's request is processed, U ser2 has to update the local copy, and therefore the update procedure is applied. First the document level history of the local document is analysed. Because no remote operations of paragraph level have to be merged, the update is then applied for the paragraph level by analysing the history of paragraph 1. There are no remote operations of sentence level, so the processing is applied for the sentence level. There are no operations referring to sentence 2, so we will analyse the merging for sentence 1. Operation O12 is of word level, and because there are no local operations of word level, O12 will keep its original form. The update procedure will be recursively applied for each of the words belonging to sentence 1. We will analyse only the update applied for the second word of sentence 1, since the remote logs corresponding to the other words in the sentence are empty. The merge procedure will be applied between the list of operations consisting of O11 and the list consisting of O22. O11 and O22 are con°icting and according to the assumed policy the local operation will be kept. As result of this merging, the newLocalLog, i.e. the list of operations to be transmitted to the repository, will be [inv(O11); O22] and the newRemoteLog, i.e. the list of operations to be applied on the local copy of the document will be empty. Therefore, the new local version of the document in the workspace of U ser2 will be \Absence increases the great loves. And diminishes small ones." This will be also the new version V2 of the document into the repository after U ser2 commits. D21 will become D21 = [O21; inv(O11); O22].
In order to highlight the fact that operations of higher level granularity do not need to be transformed against the operations of lower level granularity, consider the case that U ser1 updates his local version of the document with version V2. Operation O21 of sentence level does not need to be transformed against any of the local operations in the workspace of U ser1. 4
Due to the hierarchical structure of the document, in our approach the con°icts
can be de¯ned at di®erent semantic levels, as opposed to the RCS [
Other research works looked at the tree representation of documents for
asynchronous collaborative editing, such as working with XML documents. But
the merging approach described in [
In [
In this paper we proposed a tree based approach for maintaining the consistency in the case of the asynchronous collaborative text editing that o®ers also the possibility of de¯ning and resolving the con°icts at di®erent granularity levels corresponding to the document levels.