One very significant advantage of P4 over CVS is that it keeps track of what has been merged from one branch to another. As a result, the average user can successfully use branching with minimal discipline without disastrous consequences. However, this paper is intended to show that the merging process is not quite as foolproof as one might otherwise believe.
The problem is illustrated by example. The example is contrived for the sake of simplicity, but is illustrative of problems that do occur in practice.
Consider the case of two files, foo.c and bar.c . Assume that the policy for these files requires them to compile and run with a zero exit status before they are submitted. For compactness, every version of foo.c and bar.c is represented by the tuple (n1, n2, n3, n4) corresponding to the following file:
|
Now consider the sequence of events represented by the following diagram:
The final step presents a rather sticky dilemma:
| Should the second change to the branch be integrated into the trunk or not? |
By default, P4 will integrate the change because it occurred after a change that has not been previously integrated. However, this leads to state (2,2,5,2) , which is not the desired state because the second change to the trunk is permanently lost, and must be reconstructed by a future submission, after the disappearance of the change is discovered. We term this situation a retrograde merge. (The retrograde merge can take other forms as well. For example, a spurious conflict can result from adding lines that are already present but have been modified.)
The integration of the second change can be inhibited by first integrating and resolving only the first change, and then integrating the second change and resolving with -ay. However, this leads to state (2,2,4,1) , which is not the desired state because it runs with an assertion failure. The work of diagnosing and fixing the failure must be replicated before the change can be submitted. In real life, this might represent a significant amount of work, especially if the person doing the trunk merge is not the same as the person who did the branch merge. We term this situation a rejected resolution.
It is observed that the P4's default behavior is heuristically correct, in the sense that it implements what is usually the lesser of two evils, assuming that retrograde merges are usually less troublesome than rejected resolutions. However, the behavior is still less than optimal, and because retrograde merges are never detected and brought to the attention of the user, constant vigilance is required to correct them before they propagate into workspaces and other branches.
It is already well-known that merging changes between codelines that aren't branched from each other is troublesome. (See Perforce NOTE009.)
While the rules that P4 uses to merge among branches are well-specified, the burden of figuring out which changes ought to be merged still falls primarily on the user. The simplest policy is simply to merge any changes that are not known to be already merged. The main drawback to this approach is the frequency of retrograde merges.
For example, consider the sequence of events represented by the following diagram:
The final step results in the second edit to the trunk file (step 6) being permanently lost. What happened here is that an earlier change to the target file that had been countermanded was nonetheless reflected back into the target file and produced a retrograde merge. Instead, the source revision should have been considered previously integrated and not merged.
Merging indiscriminately is relatively safe when all the changes in the target codeline have been previously merged into the source codeline, because any retrograde merges will then appear as conflicts. However, it is often the case that one does not want to merge all such changes into the source codeline. Furthermore, it might not be possible to satisfy this safety criterion while merging all such changes into the source codeline, because the source codeline might itself have changes that were merged from other codelines.
Other possible solutions might involve protocols for specifying additional information in the change list description and/or notifying potentially affected parties via email when merges occur. Such policies probably involve too much overhead and require too much unenforced discipline to be successful in practice.
The most obvious interpretation of "previously integrated" would be that there exists an integration record from the source revision to the target file. However, this interpretation does not account for integrate's behavior.
In reality, a source revision is also considered previously integrated under any of the following conditions:
It is worth noting that both submitted integration records and unsubmitted integrations in the current client are considered. If an unsubmitted integration has been resolved, then its type is known. Otherwise, its type is assumed to be "merge" unless it is known to be "branch" or "delete" based on the existence or nonexistence of the source and target.
Another undocumented feature is that pending resolves are always performed in increasing source file revision order, regardless of the order in which they were scheduled by p4 integrate.
When you do the resolve, YOURS is clearly the version in the
client prior to the resolve.
However, BASE and THEIRS are somewhat murky.
It turns out that if -f is not passed to p4 integrate,
then BASE is always the revision prior to the
first unintegrated candidate source revision, and THEIRS is
always the last candidate source revision.
"But what about subtracting previously integrated revisions?" I hear you ask. Contrary to NOTE057, it doesn't always happen. Any previously integrated candidate source revisions that are preceded by candidate source revisions that have not been previously integrated are re-integrated. (Some number of the trailing candidate source revisions might be subtracted even if they follow an unintegrated revision, but only if they are each considered previously integrated due to an "ignore" integration record. The exact conditions under which this occurs do not follow an obvious pattern.)
As we saw in the example of Problem #1, re-integrating such revisions serves a valid purpose: It helps to avoid rejected resolutions. That is, if a source revision originated from the target file (i.e. it is considered previously integrated due to condition #3) and there are earlier unintegrated revisions, then the source revision may contain the resolution of conflicts, and therefore preventing it from being integrated might lead to a rejected resolution. However, this rule also gives rise to yet another problem....
Consider the sequence of events represented by the following diagram:
The final step results in a spurious conflict, because the second edit to the branch was integrated even though it had already been integrated in step 4. This needn't have happened, because the second edit to the branch has already been declared not applicable to the trunk by virtue of being resolved with -ay. The final state should have been (3,3) instead of (conflict,3) .
Problem #1 illustrates that the handling of source revisions that originated (at least partially) from the target file needs refinement. Neither integrating nor ignoring them necessarily produces the desired result. A more sophisticated strategy must be employed to avoid these problems.
Problem #2 illustrates that simply tracking the integration history between pairs of files does not necessarily provide enough information to determine what needs to be integrated.
Problem #3 illustrates that it is necessary to distinguish revisions that are considered previously integrated only because they originated in the target file (condition #3) from files that are considered previously integrated for other reasons.
It is possible to avoid all of these problems by conforming to the following discipline:
However, it is recognized that this discipline is too restrictive to follow without exception. For example, it does not support rejecting a change from the trunk to the branch or vice-versa. Also, it does not permit accumulation branches (see Advanced SCM Branching Strategies).
It is believed that all of these flaws are overcome by the following changes to p4:
It is proposed that a new type of integration record called "update" be
added to the database format.
"Update" integration records are added in lieu of "copy" or "merge" records
whenever YOURS is identical to BASE.
Such records indicate that the source revision is contained in the target
revision (as with a "merge" record), and that the result was identical
to the final source revision (as with a "copy" record).
The usefulness of this new type of integration record will become apparent
shortly.
A source revision R1 is considered unconditionally integrated into a target revision R2 if and only if any of the following conditions holds:
A source revision R is considered conditionally integrated into a target file F if and only if there exists an integration record from F to R, and there does not exist an integration record from any file other than F to R.
In order to determine relationships among multiple branches for the case in which "tributary flow" is violated, what is required is a transitive closure of the "unconditionally integrated" and "contained" properties:
Unfortunately, transitive closure is potentially expensive to compute. This may not pose a real problem in practice, because the maximally connected subgraphs of the integration record graph are expected to be small (i.e. no more than 100 related files). Also, the closure could be stored in the database and computed incrementally. There may also be other ways to compute this inexpensively of which I am unaware.
If you're willing to leave Problem #2 unsolved instead, you can consider "transitively integrated" and "transitively contained" synonymous with "unconditionally integrated" and "contained," respectively, for the remainder of the proposal.
A candidate source revision is considered fully integrated into the target file if and only if any of the following conditions hold:
Note that ignore integration records are not transitive. That is, integrating from a codeline that rejected a change does not imply rejecting the change from the target codeline.
Now we're getting to the interesting part:
| It is proposed that a single p4 integrate (without -f) may schedule multiple resolves. |
A resolve is scheduled for each contiguous range of candidate source
revisions that have not been fully integrated.
For each such range, BASE is the source revision prior to the
beginning the range, and THEIRS is the source revision at the
end of the range, subject to modifications described below.
A separate integration record is created for each such resolve.
For each such resolve, an inverse resolve is scheduled for each
contiguous range of target revisions that are transitively contained
in a candidate source revision.
An inverse resolve is also scheduled for every contiguous range of revisions
that are transitively contained both in a candidate source revision, and
in either a remaining target revision or a revision
that has an ignore integration record to a remaining target revision.
For each such range, YOURS is the THEIRS file
for the normal (non-inverse) resolve, BASE is the revision
at the end of the range, and THEIRS is the revision prior
to the beginning of the range.
After an inverse resolve is resolved, a modified THEIRS file is
generated.
After all inverse resolves for a normal resolve are resolved, the normal
resolve is then performed with the resulting THEIRS file.
No integration records are created for inverse resolves.
Inverse resolves are always performed in reverse target revision order, regardless of the order of the source revisions in which they appear.
It is apparent that the proposed solution fixes Problems #2 and #3. However, Problem #1 merits some discussion.
In the final integration to the trunk, the following happens:
THEIRS is (2,2,5,2) .
After the inverse resolve, the state of THEIRS is (1,2,5,1) .
If unrelated changes occur within a single revision, then integrating that revision into another codeline may require partially rejecting the revision. In that case, declaring the integration either merged or ignored is at best only approximately accurate. This generally results in p4 integrate doing something undesirable. The only apparent remedy is either not to mix unrelated changes at the codeline of origin, or not to reject changes.
If source revisions are merged out-of-order, then the target file may contain
conflicts due to the absence of the earlier yet-to-be-integrated changes.
Such conflicts are resolved by editing the file to "un-resolve" those
revisions.
Under the proposed behavior, when the remaining revisions are integrated, the
already integrated later revisions are not normally considered.
Generally, this results in new conflicts that are resolved by manually
undoing the un-resolve.
Arguably, it is preferable that those later revisions are re-integrated such
that the result of un-un-resolving can be gleaned from the
THEIRS file.
(Consider the example of Problem #1, modified such that the second change in the branch originates in the branch and is merged to the first change in the trunk, instead of vice-versa.)
Unfortunately, a policy that causes this to happen without also causing retrograde merges is not apparent. Given that out-of-order merging is expected to be relatively rare, and that re-integrating does not necessarily produce the correct result either, the proposed behavior is alleged to be preferred.