[MERGE] status command analysis

[Robert Collins]

-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
# Bazaar merge directive format 1
# revision_id: robertc at robertcollins.net-20070702023128-\
#   5j3rtf8bx5v49tbi
# target_branch: http://bazaar-vcs.org/bzr/bzr.dev
# testament_sha1: baeb76aaf673dbc7038b19dbd492f6c1331c341d
# timestamp: 2007-07-02 12:32:19 +1000
# source_branch: sftp://rookery/~/public_html/baz2.0/repository
# 
# Bazaar revision bundle v0.9
#
# message:
#   Status analysis.
# committer: Robert Collins <robertc at robertcollins.net>
# date: Mon 2007-07-02 12:31:28.618999958 +1000

=== added file doc/developers/status.txt // file-id:status.txt-20070702023117-6
... xss29lx170qndwr-1
--- /dev/null
+++ doc/developers/status.txt
@@ -0,0 +1,84 @@
+The status command
+==================
+
+The status command is used to provide a pithy listing of the changes between
+two trees. Its common case is between the working tree and the basis tree, but
+it can be used between any two arbitrary trees.
+
+.. contents:: :local:
+
+UI Overview
+-----------
+
+Status shows several things in parallel (for the paths the user supplied mapped
+across the from and to tree, and any pending merges in the to tree).
+
+1. Single line summary of all new revisions - the pending merges and their
+   parents recursively.
+2. Changes to the tree shape - adds/deletes/renames.
+3. Changes to versioned content - kind changes and content changes.
+
+Ideal work for working tree to historical status
+------------------------------------------------
+
+We need to do the following things at a minimum:
+
+1. Determine new revisions - the pending merges and history.
+
+1. Retrieve the first line of the commit message for the new revisions.
+
+1. Determine the tree differences between the two trees using the users paths
+   to limit the scope, and resolving paths in the trees for any pending merges.
+   We arguably don't care about tracking metadata for this - only the value of
+   the tree the user commited.
+
+Expanding on the tree difference case we will need to:
+
+1. Stat every path in working trees which is included by the users path
+   selection to ascertain kind and execute bit.
+
+1. For paths which have the same kind in both trees and have content, read
+   that content or otherwise determine whether the content has changed. Using
+   our hash cache from the dirstate allows us to avoid reading the file in the
+   common case. There are alternative ways to achieve this - we could record
+   a pointer to a revision which contained this fileid with the current content
+   rather than storing the content's hash; but this seems to be a pointless 
+   double-indirection unless we save enough storage in the working tree.
+
+
+Locality of reference
+---------------------
+
+- We should stat files in the same directory without reading or statting
+files in other directories.
+
+- We should read files in the same directory without reading or writing
+files in other directories - and note this is separate to statting (file
+data is usually physically disjoint to metadata).
+
+
+Scaling observations
+--------------------
+
+- The stat operation clearly involves every versioned path in the common case.
+- Expanding out the users path selection in a naive manner involves reading the
+  entire tree shape information for both trees and for all pending-merge trees.
+  (Dirstate makes this tolerably cheap for now, but we're still scaling
+  extra-linearly.)
+- The amount of effort required to generate tree differences between the
+  working tree and the basis tree is interesting: with a tree-like structure
+  and some generatable name for child nodes we use the working tree data to
+  eliminate accessing or considering subtrees regardless of historival
+  age. However, if we have had to access the historical tree shape to
+  perform path selection this rather reduces the win we can obtain here.
+  If we can cause path expansion to not require historical shape access
+  (perhaps by performing the expansion after calculating the tree
+  difference for the top level of the selected path) then we can gain a
+  larger win. This strongly suggests that path expansion and tree
+  difference generation should be linked in terms of API.
+ 
+
+
+..
+   vim: ft=rst tw=74 ai
+

=== modified file doc/developers/performance-roadmap.txt
--- doc/developers/performance-roadmap.txt
+++ doc/developers/performance-roadmap.txt
@@ -42,6 +42,8 @@
 
 .. include:: revert.txt
 
+.. include:: status.txt
+
 .. include:: annotate.txt
 
 .. include:: merge-scaling.txt

=== modified file doc/developers/performance.dot
--- doc/developers/performance.dot
+++ doc/developers/performance.dot
@@ -12,11 +12,11 @@
   gc_analysis[label="Work required analysis for gc"];
   revert_analysis[label="Work required analysis for revert"];
   revert_path_analysis[label="Work required analysis for revert of selected paths"];
+  status_analysis[label="Work required analysis for status"];
   wt_disk_order[label="Working Tree disk ordering\n6-8 weeks"];
 
   /* uncompleted node list - add new tasks here */
   node[color="blue"];
-  status_analysis[label="Work required analysis for status"];
   log_analysis[label="Work required analysis for log"];
   log_path_analysis[label="Work required analysis for log of selected paths."];
   diff_analysis[label="Work required analysis for diff"];

=== modified directory  // last-changed:robertc at robertcollins.net-2007070202312
... 8-5j3rtf8bx5v49tbi
# revision id: robertc at robertcollins.net-20070702023128-5j3rtf8bx5v49tbi
# sha1: baeb76aaf673dbc7038b19dbd492f6c1331c341d
# inventory sha1: 184d697bcdbe4b64b87dda36a7d429cd31e0b298
# parent ids:
#   pqm at pqm.ubuntu.com-20070629150144-xoeghcfb52pit8tv
# base id: pqm at pqm.ubuntu.com-20070629150144-xoeghcfb52pit8tv
# properties:
#   branch-nick: repository

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20070702/75eca0eb/attachment.pgp