| This branch exists for the implementation of the svn bisect command. |
| It is maintained as a reintegrate-able branch with regular catch-up |
| merges from trunk. |
| |
| PURPOSE |
| ======= |
| |
| For years, subversion users have used third-party scripts to do what |
| should rightfully be a part of Subversion itself. This branch aims |
| to implement bisect functionality and make it available via the |
| public API. |
| |
| |
| SPEC |
| ==== |
| |
| svn bisect start [-rN[:M]] [--term-old=good] [--term-new=bad] |
| ------------------------------------------------------------- |
| |
| Initialize the bisection state. |
| If a state already exists, clean it up and create a fresh one. |
| If a revision range is specified, limit bisection to this range. |
| If a single revision is specified, bisect from that revision to HEAD. |
| If no revision is specified, bisect from revision 1 to HEAD. |
| |
| The "--term-old" and/or "--term-new" options allow the use of other |
| terms besides "good" and "bad" with svn bisect. This is useful when |
| running a bisection for some other reason than to find the revision |
| that introduced a bug. Any term can be used but existing Subversion |
| command and option strings cannot be used. |
| |
| |
| svn bisect bad [-rN] |
| -------------------- |
| |
| If used before "svn bisect run", mark the specified revision as "bad". |
| |
| If used during interactive bisection, no revision should be specified. |
| The current revision is marked as "bad". |
| |
| If the "--term-new" option was given to "svn bisect start" with a |
| value other than "bad", then replace "bad" with the term given. |
| |
| |
| svn bisect good [-rN] |
| --------------------- |
| |
| If used before "svn bisect run", mark the specified revision as |
| "good". |
| |
| If used during interactive bisection, no revision should be |
| specified. The current revision is marked as "good". |
| |
| If the "--term-old" option was given to "svn bisect start" with a |
| value other than "good", then replace "good" with the term given. |
| |
| |
| svn bisect skip [-rN[:M]] |
| ------------------------- |
| |
| If specified before "svn bisect run", mark the specified revision or |
| revision range as "skip". |
| |
| If used during the interactive bisection, the current revision will |
| be marked "skip", and a nearby revision will be chosen. See below. |
| |
| |
| svn bisect reset [-rN] |
| ---------------------- |
| |
| Update the working copy to the specified revision and clean the |
| bisection state. If no revision is specified, it takes the working |
| copy to the revision before "svn bisect start" was run. |
| |
| |
| svn bisect run [my_script [args]] |
| --------------------------------- |
| |
| Start the bisection. If no script is given, start the bisect in |
| interactive mode. i.e after updating to a specific revision, wait |
| for the user to manually run tests and mark the revision as good, |
| bad or skip. |
| |
| |
| Test Script Exit Codes |
| ---------------------- |
| |
| The user-provided script's exit codes should follow this spec: |
| |
| Good revision : Exit Code 0 |
| Bad revision : Exit Code 1 thru 127 (except 125) |
| Skip revision : Exit Code 125 |
| Abort bisection : Any other Exit Code |
| |
| The above mentioned exit codes conform to the way git bisect does |
| things. |
| |
| |
| HOW TO USE |
| ========== |
| |
| 1. Have a checked out working copy. |
| |
| 2. In the working copy, navigate to the directory in which the |
| bisection will run. This may be the root directory of the working |
| copy or any subdirectory. |
| |
| 3. Run 'svn bisect start [-rN[:M]]' to set the initial bounds for the |
| bisection. |
| |
| 4. Optionally, run one or more invocation(s) of |
| 'svn bisect skip -rN[:M] to mark revisions for explicit skipping. |
| |
| 5. Interactive mode: |
| a. Run 'svn bisect run' with no script argument. |
| b. Subversion will choose a revision and update to it. |
| c. Test the revision. |
| d. Based on the result of the test, run 'svn bisect good', |
| 'svn bisect bad', or 'svn bisect skip' with no argument. |
| e. If there are no more revisions to test, a summary is printed |
| which identifies the sought-after revision and this process |
| ends. Otherwise, repeat from step 5a (run 'svn bisect run', |
| etc). |
| |
| 6. Automatic mode: |
| a. Run 'svn bisect run' with a script argument. |
| b. Subversion will repeatedly update the working copy to various |
| revisions and run the script at each revision it chooses. |
| c. By means of its exit code, the script will tell Subversion |
| whether this is a good, bad, or skip revision, or whether the |
| bisection should abort due to a fatal error. |
| d. When there are no more revisions to test, a summary is printed |
| which identifies the sought-after revision and the bisection |
| ends. |
| |
| |
| THE GOOD, THE BAD, AND THE SKIPPED |
| ================================== |
| |
| As explained above, certain aspects are inspired by Git (such as the |
| test script's return codes that signify Good, Bad, Skip, and Abort). |
| |
| But Subversion knows a few tricks that Git doesn't, such as the |
| ability to operate on subsets of repositories. This ability makes it |
| possible to house multiple projects in a single repository. |
| Subversion's own source code lives in such a "megarepo" alongside |
| other ASF projects. This also makes it possible to operate on a subset |
| of a project, such as, say, the documentation, which could reside in a |
| subdirectory of a project's main directory). This is also Subversion's |
| branching model. |
| |
| This is relevant to the design of a bisect feature because it means |
| that between any two revisions, there may be numerous revisions in |
| which nothing changes. In those revisions, changes were made in other |
| parts of the repository and did not touch the subset being operated |
| on. |
| |
| Thus, there are two reasons why a revision should be skipped: |
| |
| (1) The revision is implicitly skipped if it is not "operative" |
| (defined below). |
| |
| (2) The revision is explicitly skipped if the user or the user's test |
| script tell us to skip it. |
| |
| Both of these are handled by the algorithm. See below. |
| |
| |
| DEFINITIONS |
| =========== |
| |
| 1. Operative: For the purposes of this bisect feature, a revision is |
| "operative" if something changes during that revision in the |
| directory in which 'svn bisect' is run and/or its subdirectories. |
| 'Something' can mean file content changes, property changes, |
| and/or tree changes. In other words, if 'svn diff -rN:M-1' |
| produces no output, then there are no operative revisions between |
| N and M (though revision M could be operative). |
| |
| |
| PERSISTENCE RECORD |
| ================== |
| |
| In the case of interactive bisection, the svn client exits after each |
| invocation. Therefore, a working copy persistence record is needed. |
| |
| Record contents: |
| * N and M: Revision numbers representing the initial bounds as given |
| by user at 'svn bisect start'. These are constants for the duration |
| of the bisection. |
| * n, m, r: Revision numbers representing the current bounds (n, m) |
| and revision being tested (r). Note that n < r < m. |
| * Set of 'good' revisions. |
| * Set of 'bad' revisions. |
| * Set of 'skip' revisions. |
| * Set of tested revisions. |
| * ZigZag: An integer, either 1 or -1, used for zig-zagging around |
| skipped revisions in search of a revision to test. |
| |
| Notes: |
| (1) Names are subject to change. |
| (2) The storage format for the above "sets" is not yet determined. |
| |
| |
| ALGORITHM |
| ========= |
| |
| Notes: |
| (1) This algorithm is a work in progress. |
| (2) The pseudocode below is not written according to any standard. |
| |
| Let n, m, r be revision numbers, where n < r < m. |
| |
| |
| svn bisect start [-rN:M] |
| ------------------------ |
| |
| 1. If N is specified, set n = N. Otherwise set n = 1. |
| |
| 2. If M is specified, set m = M. Otherwise set m = HEAD. |
| |
| 3. Sanity check: |
| a. Make sure the repository contains at least r1 through r4. |
| Otherwise it makes no sense to run a bisection! |
| b. Make sure M > N + 1. Otherwise it makes no sense to run a |
| bisection! |
| |
| 4. Initialize r = 0. |
| |
| 5. Initialize sets of good, bad, skip, and tested revisions to empty |
| sets. |
| |
| 6. Write persistence record to wc. |
| |
| |
| svn bisect skip [-rN[:M]] |
| ------------------------- |
| |
| 1. If no persistence record, 'svn bisect start' was not run; report |
| error and exit. |
| |
| 2. Mark the given revision(s) as 'skip' (i.e., record their numbers |
| in the set of 'skip' revisions. |
| |
| |
| Function: Find Middle Revision(n, m): |
| ------------------------------------- |
| |
| 1. If n >= (m - 1), return error code. |
| |
| 2. Calculate X = number of operative revisions between n and m, not |
| including n and m. |
| |
| 3. If X == 0, return error code. |
| |
| 4. Set s = (ceil(X/2))th operative revision after n. |
| |
| 5. Return that revision number. |
| |
| |
| Function: Find Alternate Middle Revision(n, m, r): |
| -------------------------------------------------- |
| |
| 1. If n >= (m - 1), return error code. |
| |
| 2. ZigZag = -ZigZag |
| |
| 3. If ZigZag > 0: |
| a. Set s = next operative revision after r. |
| b. If s >= m, set s = previous operative revision before r. |
| c. If s <= n, return error code. |
| |
| 4. If ZigZag < 0: |
| a. Set s = previous operative revision before r. |
| b. If s <= n, set s = next operative revision after r. |
| c. If s >= m, return error code. |
| |
| 5. Return s |
| |
| |
| Function: Choose Revision To Test(n, m): |
| ---------------------------------------- |
| |
| 1. Set r = Find Middle Revision. If error, return error code. |
| |
| 2. If r is an operative revision, return r. |
| |
| 3. Set r = Find Alternate Middle Revision. |
| If error, return error code. |
| |
| 4. Return r. |
| |
| |
| svn bisect run [script] |
| ----------------------- |
| |
| 1. If script specified, automatic mode else interactive mode. |
| |
| 2. Adjust n and m to operative revisions and ensure they do not meet |
| or cross: |
| a. If n >= (m - 1), report error and exit. |
| b. If revision n is not operative, set n to the next operative |
| revision > n. |
| c. If n >= (m - 1), report error and exit. |
| d. If revision m is not operative, set m to the previous operative |
| revision < m. |
| e. If m < n, report error and exit. |
| |
| 3. Set r = Choose Revision To Test. If error: |
| a. If revisions have been tested, revision m is the sought after |
| revision. Go to step 11. |
| b. Otherwise, there are no revisions to test. Report error and |
| exit. |
| |
| 4. Update to revision r. |
| |
| 5. If interactive mode, exit. User should test and run appropriate |
| commands. |
| |
| 6. Run script. |
| |
| 7. If script reports 'error': |
| a. The bisection is terminated. |
| b. Report error and exit. |
| |
| 8. If script reports 'good': |
| a. Add revision r to 'good' set. |
| b. Set n = r. |
| c. Set r = Choose Revision To Test. If error, revision m is the |
| sought after revision. Go to step 11. |
| d. Go to step 4. |
| |
| 9. If bad: |
| a. Add revision r to 'bad' set. |
| b. Set m = r. |
| c. Set r = Choose Revision To Test. If error, revision m is the |
| sought after revision. Go to step 11. |
| d. Go to step 4. |
| |
| 10. If skip: |
| a. Add revision r to 'skip' set. |
| b. Set s = Find Alternate Middle Revision. |
| c. If error, revision m is the sought after revision. Go to |
| step 11. |
| d. Set r = s. |
| e. Go to step 4. |
| |
| 11. Found the sought after revision. |
| a. Print report, which may be some combination of: |
| - The initial bounds N and M as given to "svn bisect start". |
| - Which revisions were found 'good', 'bad', and 'skip'. |
| - Summary: The sought after revision and how many revisions |
| were tested to find it. |
| b. Clean up persistence structure. The bisection is complete. |
| |
| |
| MILESTONES |
| ========== |
| |
| This part of the document serves as a progress tracker by defining |
| the milestones that need to be completed. It contains a set of phases, |
| each with it's own tasks. |
| |
| |
| PHASE 1 |
| ------- |
| |
| Task Status |
| |
| 1.1 Write skeleton code with bare minimum [Started] |
| implementation. This involves creating |
| the new source files in the various |
| modules and the skeleton API. |
| |
| 1.2 Define a set of unit tests to clearly [Started] |
| define the expected behaviour. This |
| will be an on-going task and will not |
| be a phase blocker. |
| |
| 1.3 Implement the tests. [Not Started] |
| |
| |
| PHASE 2 |
| ------- |
| |
| Task Status |
| |
| 2.1 Implement the behaviour as defined by [Not Started] |
| the test suite. |
| |
| 2.2 Check for consistency of code, error [Not Started] |
| handling and error codes. |
| |
| |
