Merge lp:~abentley/bzr/unbreak-merge into lp:bzr/2.0

[Aaron Bentley]

[Aaron Bentley (abentley)]

Hi all,

This branch fixes merge so that it works when the this_tree is not a
working tree. The ConfigurableFileMerger was using merger.this_tree.branch, to
retrieve the configuration, but it should actually use merger.this_branch.

The test simply shows that generating a preview transform with a RevisionTree
as the this_tree does not raise an exception.

[John A Meinel (jameinel)]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Aaron Bentley wrote:
> Aaron Bentley has proposed merging lp:~abentley/bzr/unbreak-merge into lp:bzr/2.0.
>
> Requested reviews:
> bzr-core (bzr-core)
>
>
> Hi all,
>
> This branch fixes merge so that it works when the this_tree is not a
> working tree. The ConfigurableFileMerger was using merger.this_tree.branch, to
> retrieve the configuration, but it should actually use merger.this_branch.
>
> The test simply shows that generating a preview transform with a RevisionTree
> as the this_tree does not raise an exception.The attached diff has been truncated due to its size.
>

 review: needs_fixing

I don't know why you proposed it into 2.0, given that this only exists
in 2.1. I'm guessing you just need to resubmit vs the 2.1 branch.
The discussion seems fine.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkt8hfMACgkQJdeBCYSNAAM+6gCgz6ys8C4wk4VP/1IUcKjU0a1D
MvwAoJHN0QnqkQT6ojX/SYmOXGFbzoG2
=6RG9
-----END PGP SIGNATURE-----

review: Needs Fixing

[Aaron Bentley (abentley)]

Robert told me to JFDI, so it's playing in PQM (against 2.1) now.

Unmerged revisions

4817. By Aaron Bentley on 2010-02-18

Restore progress import.

4816. By Aaron Bentley on 2010-02-17

Fix merge when this_tree is not a WorkingTree.

4815. By Canonical.com Patch Queue Manager <email address hidden> on 2010-02-17

(Matt Nordhoff) Standardize the exceptions when creating a new
 StaticTuple (bug #457979)

4814. By Canonical.com Patch Queue Manager <email address hidden> on 2010-02-17

(mbp) Register SIGWINCH only when creating a TextUIFactory

4813. By Canonical.com Patch Queue Manager <email address hidden> on 2010-02-16

(jam) Release 2.1.0 final

4812. By Canonical.com Patch Queue Manager <email address hidden> on 2010-02-12

(andrew) Merge lp:bzr/2.0 into lp:bzr/2.1, including fixes for #337834,
 #368931, and #423563.

4811. By Canonical.com Patch Queue Manager <email address hidden> on 2010-02-11

(andrew) Replace several fragile try/finally blocks in merge.py using
 bzrlib.cleanup. (#517275)

4810. By Canonical.com Patch Queue Manager <email address hidden> on 2010-02-11

(andrew) Replace several fragile try/finally blocks in merge.py using
 bzrlib.cleanup. (#517275)

4809. By Canonical.com Patch Queue Manager <email address hidden> on 2010-02-10

(jelmer) Fix formatting of foreign revision properties

4808. By Canonical.com Patch Queue Manager <email address hidden> on 2010-02-04

(vila) Stop requiring testtools for sftp use

=== modified file '.bzrignore'
--- .bzrignore	2009-09-09 11:43:10 +0000
+++ .bzrignore	2010-02-18 00:00:52 +0000
@@ -58,6 +58,9 @@
 bzrlib/_known_graph_pyx.c
 bzrlib/_readdir_pyx.c
 bzrlib/_rio_pyx.c
+bzrlib/_simple_set_pyx.c
+bzrlib/_simple_set_pyx.h
+bzrlib/_simple_set_pyx_api.h
 bzrlib/_walkdirs_win32.c
 # built extension modules
 bzrlib/_*.dll

=== modified file 'Makefile'
--- Makefile	2009-11-18 04:29:56 +0000
+++ Makefile	2010-02-18 00:00:52 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2005, 2006, 2007, 2008, 2009 Canonical Ltd
+# Copyright (C) 2005-2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -40,8 +40,6 @@
 
 check-nodocs: extensions
 	$(PYTHON) -Werror -O ./bzr selftest -1v $(tests)
-	@echo "Running all tests with no locale."
-	LC_CTYPE= LANG=C LC_ALL= ./bzr selftest -1v $(tests) 2>&1 | sed -e 's/^/[ascii] /'
 
 # Run Python style checker (apt-get install pyflakes)
 #
@@ -201,7 +199,6 @@
 
 # translate txt docs to html
 derived_txt_files = \
-	doc/en/user-reference/bzr_man.txt \
 	doc/en/release-notes/NEWS.txt
 txt_all = \
 	doc/en/tutorials/tutorial.txt \
@@ -214,6 +211,7 @@
 	doc/ja/tutorials/centralized_workflow.txt \
 	$(wildcard doc/*/mini-tutorial/index.txt) \
 	$(wildcard doc/*/user-guide/index-plain.txt) \
+	doc/en/admin-guide/index-plain.txt \
 	$(wildcard doc/es/guia-usario/*.txt) \
 	$(derived_txt_files) \
 	doc/en/upgrade-guide/index.txt \
@@ -223,7 +221,8 @@
 	doc/en/user-guide/index.txt \
 	doc/es/user-guide/index.txt \
 	doc/ja/user-guide/index.txt \
-	doc/ru/user-guide/index.txt
+	doc/ru/user-guide/index.txt \
+	doc/en/admin-guide/index.txt
 txt_files = $(filter-out $(txt_nohtml), $(txt_all))
 htm_files = $(patsubst %.txt, %.html, $(txt_files)) 
 
@@ -281,6 +280,9 @@
 #doc/ru/user-guide/index.html: $(wildcard $(addsuffix /*.txt, doc/ru/user-guide)) 
 #	$(rst2html) --stylesheet=../../default.css $(dir $@)index.txt $@
 #
+doc/en/admin-guide/index-plain.html: $(wildcard $(addsuffix /*.txt, doc/en/admin-guide)) 
+	$(rst2html) --stylesheet=../../default.css $(dir $@)index-plain.txt $@
+
 doc/developers/%.html: doc/developers/%.txt
 	$(rst2html) --stylesheet=../default.css $< $@
 
@@ -293,9 +295,6 @@
 %.html: %.txt
 	$(rst2html) --stylesheet=../../default.css $< $@
 
-doc/en/user-reference/bzr_man.txt: $(MAN_DEPENDENCIES)
-	$(PYTHON) tools/generate_docs.py -o $@ rstx
-
 doc/en/release-notes/NEWS.txt: NEWS
 	$(PYTHON) -c "import shutil; shutil.copyfile('$<', '$@')"
 
@@ -409,7 +408,7 @@
 
 .PHONY: dist dist-upload-escudero check-dist-tarball
 
-# build a distribution tarball and zip file.
+# build a distribution source tarball
 #
 # this method of copying the pyrex generated files is a bit ugly; it would be
 # nicer to generate it from distutils.
@@ -419,15 +418,12 @@
 	expbasedir=`mktemp -t -d tmp_bzr_dist.XXXXXXXXXX` && \
 	expdir=$$expbasedir/bzr-$$version && \
 	tarball=$$PWD/../bzr-$$version.tar.gz && \
-	zipball=$$PWD/../bzr-$$version.zip && \
 	$(MAKE) clean && \
 	$(MAKE) && \
 	bzr export $$expdir && \
-	cp bzrlib/*.c $$expdir/bzrlib/. && \
+	cp bzrlib/*.c bzrlib/*.h $$expdir/bzrlib/. && \
 	tar cfz $$tarball -C $$expbasedir bzr-$$version && \
-	(cd $$expbasedir && zip -r $$zipball bzr-$$version) && \
 	gpg --detach-sign $$tarball && \
-	gpg --detach-sign $$zipball && \
 	rm -rf $$expbasedir
 
 # run all tests in a previously built tarball
@@ -445,15 +441,10 @@
 dist-upload-escudero:
 	version=`./bzr version --short` && \
 	tarball=../bzr-$$version.tar.gz && \
-	zipball=../bzr-$$version.zip && \
-	scp $$zipball $$zipball.sig $$tarball $$tarball.sig \
+	scp $$tarball $$tarball.sig \
 	    escudero.ubuntu.com:/srv/bazaar.canonical.com/www/releases/src \
 		&& \
 	echo verifying over http... && \
-	curl http://bazaar-vcs.org/releases/src/bzr-$$version.zip \
-		| diff -s - $$zipball && \
-	curl http://bazaar-vcs.org/releases/src/bzr-$$version.zip.sig \
-		| diff -s - $$zipball.sig 
 	curl http://bazaar-vcs.org/releases/src/bzr-$$version.tar.gz \
 		| diff -s - $$tarball && \
 	curl http://bazaar-vcs.org/releases/src/bzr-$$version.tar.gz.sig \

=== modified file 'NEWS'
--- NEWS	2010-02-12 06:00:33 +0000
+++ NEWS	2010-02-18 00:00:52 +0000
@@ -5,6 +5,348 @@
 .. contents:: List of Releases
    :depth: 1
 
+
+bzr 2.1.1
+#########
+
+:2.1.1: not released yet
+
+Bug Fixes
+*********
+
+* Register SIGWINCH handler only when creating a ``TextUIFactory``; avoids
+  problems importing bzrlib from a non-main thread.
+  (Elliot Murphy, #521989)
+
+* Standardize the error handling when creating a new ``StaticTuple``
+  (problems will raise TypeError). (Matt Nordhoff, #457979)
+
+* Merge correctly when this_tree is not a WorkingTree.  (Aaron Bentley)
+
+
+bzr 2.1.0
+#########
+
+:Codename: Strasbourg
+:2.1.0: 2010-02-11
+
+This release marks our second long-term-stable series. The Bazaar team
+has decided that we will continue to make bugfix-only 2.0.x and 2.1.x
+releases, along with 2.2 development releases. 
+
+This is a fairly incremental update, focusing on polish and bugfixing.
+There are no changes for supported disk formats. Key updates include
+reduced memory consumption for many operations, a new per-file merge
+hook, ignore patterns can now include '!' to exclude files, globbing
+support for all commands on Windows, and support for addressing home
+directories via ``bzr+ssh://host/~/`` syntax.
+
+Users are encouraged to upgrade from the 2.0 stable series.
+
+Bug Fixes
+*********
+
+* Don't require testtools to use sftp.
+  (Vincent Ladeuil, #516183)
+
+* Fix "AttributeError in Inter1and2Helper" during fetch.
+  (Martin Pool, #513432)
+
+* Ignore ``KeyError`` from ``remove_index`` during ``_abort_write_group``
+  in a pack repository, which can happen harmlessly if the abort occurs during
+  finishing the write group.  Also use ``bzrlib.cleanup`` so that any
+  other errors that occur while aborting the individual packs won't be
+  hidden by secondary failures when removing the corresponding indices.
+  (Andrew Bennetts, #423015)
+  
+* Using the ``bzrlib.chk_map`` module from within multiple threads at the
+  same time was broken due to race conditions with a module level page
+  cache. This shows up as a KeyError in the ``bzrlib.lru_cache`` code with
+  ``bzrlib.chk_map`` in the backtrace, and can be triggered without using
+  the same high level objects such as ``bzrlib.repository.Repository``
+  from different threads. chk_map now uses a thread local cache which may
+  increase memory pressure on processes using threads.
+  (Robert Collins, John Arbash Meinel, #514090)
+
+* The new ``merge_file_content`` should now be ok with tests to avoid
+  regressions.
+  (Vincent Ladeuil, #515597)
+  
+Internals
+*********
+
+* Use ``bzrlib.cleanup`` rather than less robust ``try``/``finally``
+  blocks in several places in ``bzrlib.merge``.  This avoids masking prior
+  errors when errors like ``ImmortalPendingDeletion`` occur during cleanup
+  in ``do_merge``.
+  (Andrew Bennetts, #517275)
+
+API Changes
+***********
+
+* The ``remove_index`` method of
+  ``bzrlib.repofmt.pack_repo.AggregateIndex`` no longer takes a ``pack``
+  argument.  This argument was always ignored.
+  (Andrew Bennetts, #423015)
+
+bzr 2.1.0rc2
+############
+
+:Codename: after the bubbles
+:2.1.0rc2: 2010-01-29
+
+This is a quick-turn-around to update a small issue with our new per-file
+merge hook. We expect no major changes from this to the final 2.1.0.
+
+API Changes
+***********
+
+* The new ``merge_file_content`` hook point has been altered to provide a
+  better API where state for extensions can be stored rather than the
+  too-simple function based approach. This fixes a performance regression
+  where branch configuration would be parsed per-file during merge. As
+  part of this the included news_merger has been refactored into a base
+  helper class ``bzrlib.merge.ConfigurableFileMerger``.
+  (Robert Collins, John Arbash Meinel, #513822)
+
+
+bzr 2.1.0rc1
+############
+
+:Codename: the 'new' stable
+:2.1.0rc1: 2009-01-21
+
+This is the first stable release candidate for Bazaar's 2.1 series. From
+this point onwards, the 2.1 series will be considered stable (as the 2.0
+series) and only bugfixes are expected to be incorporated. The dozen or so
+bugfixes in the 2.0.4 release are also included in this release (along
+with more than 15 more bugfixes). Some of the interesting features are
+support for per-file merge hooks, ``bzr unshelve --preview``, support
+for using ! in ignore files to exclude files from being ignored, a small
+memory leak was squashed, and many ``ObjectNotLocked`` errors were fixed.
+This looks to be a very good start for a new stable series.
+
+
+New Features
+************
+
+* Add bug information to log output when available.
+  (Neil Martinsen-Burrell, Guillermo Gonzalez, #251729)
+
+* Added ``merge_file_content`` hook point to ``Merger``, allowing plugins
+  to register custom merge logic, e.g. to provide smarter merging for
+  particular files.
+
+* Bazaar now includes the ``news_merge`` plugin.  It is disabled by
+  default, to enable it add a ``news_merge_files`` option to your
+  configuration.  Consult ``bzr help news_merge`` for more information.
+  (Andrew Bennetts)
+  
+* ``bzr branch`` now takes a ``--bind`` option. This lets you
+  branch and bind all in one command. (Ian Clatworthy)
+
+* ``bzr switch`` now takes a ``--revision`` option, to allow switching to
+  a specific revision of a branch. (Daniel Watkins, #183559)
+
+* ``bzr unshelve --preview`` can now be used to show how a patch on the
+  shelf would be applied to the working tree.
+  (Guilherme Salgado, #308122)
+
+* ``bzr update`` now takes a ``--revision`` argument. This lets you
+  change the revision of the working tree to any revision in the
+  ancestry of the current or master branch. (Matthieu Moy, Mark Hammond,
+  Martin Pool, #45719)
+
+* ``-Dbytes`` can now be used to display the total number of bytes
+  transferred for the current command. This information is always logged
+  to ``.bzr.log`` for later inspection. (John Arbash Meinel)
+
+* New ignore patterns.  Patterns prefixed with '!' are exceptions to 
+  ignore patterns and take precedence over regular ignores.  Such 
+  exceptions are used to specify files that should be versioned which 
+  would otherwise be ignored.  Patterns prefixed with '!!' act as regular 
+  ignore patterns, but have highest precedence, even over the '!' 
+  exception patterns. (John Whitley, #428031)
+
+* The ``supress_warnings`` configuration option has been introduced to disable
+  various warnings (it currently only supports the ``format_deprecation``
+  warning). The new option can be set in any of the following locations:
+  ``bazaar.conf``, ``locations.conf`` and/or ``branch.conf``.
+  (Ted Gould, Matthew Fuller, Vincent Ladeuil)
+
+Bug Fixes
+*********
+
+* Always show a message if an OS error occurs while trying to run a
+  user-specified commit message editor.
+  (Martin Pool, #504842)
+
+* ``bzr diff`` will now use the epoch when it is unable to determine 
+  the timestamp of a file, if the revision it was introduced in is a
+  ghost. (Jelmer Vernooij, #295611)
+
+* ``bzr switch -b`` can now create branches that are located using directory
+  services such as ``lp:``, even when the branch name doesn't contain a
+  '/'.  (Neil Martinsen-Burrell, #495263)
+
+* ``bzr unshelve`` has improved messages about what it is doing.
+  (Neil Martinsen-Burrell, #496917)
+
+* Concurrent autopacking is more resilient to already-renamed pack files.
+  If we find that a file we are about to obsolete is already obsoleted, we
+  do not try to rename it, and we leave the file in ``obsolete_packs``.
+  The code is also fault tolerant if a file goes missing, assuming that
+  another process already removed the file.
+  (John Arbash Meinel, Gareth White, #507557)
+
+* Fix "Too many concurrent requests" in reconcile when network connection
+  fails.  (Andrew Bennetts, #503878)
+
+* Fixed a side effect mutation of ``RemoteBzrDirFormat._network_name``
+  that caused some tests to fail when run in a non-default order.
+  Probably no user impact.  (Martin Pool, #504102)
+
+* Fixed ``ObjectNotLocked`` error in ``bzr cat -rbranch:../foo FILE``.
+  (Andrew Bennetts, #506274)
+
+* FTP transports support Unicode paths by encoding/decoding them as utf8.
+  (Vincent Ladeuil, #472161)
+
+* Listen to the SIGWINCH signal to update the terminal width.
+  (Vincent Ladeuil, #316357)
+
+* Progress bars are now hidden when ``--quiet`` is given.
+  (Martin Pool, #320035)
+
+* ``SilentUIFactory`` now supports ``make_output_stream`` and discards
+  whatever is written to it.  This un-breaks some plugin tests that
+  depended on this behaviour.
+  (Martin Pool, #499757)
+
+* When operations update the working tree, all affected files should end
+  up with the same mtime. (eg. when versioning a generated file, if you
+  update the source and the generated file together, the generated file
+  should appear up-to-date.)
+  (John Arbash Meinel, Martin <gzlist>, #488724)
+
+Improvements
+************
+
+* Added ``add_cleanup`` and ``cleanup_now`` to ``bzrlib.command.Command``.
+  All the builtin commands now use ``add_cleanup`` rather than
+  ``try``/``finally`` blocks where applicable as it is simpler and more
+  robust.  (Andrew Bennetts)
+
+* All except a small number of storage formats are now hidden, making
+  the help for numerous commands far more digestible. (Ian Clatworthy)
+
+* Attempts to open a shared repository as a branch (e.g. ``bzr branch
+  path/to/repo``) will now include "location is a repository" as a hint in
+  the error message.  (Brian de Alwis, Andrew Bennetts, #440952)
+
+* Push will now inform the user when they are trying to push to a foreign 
+  VCS for which roundtripping is not supported, and will suggest them to 
+  use dpush. (Jelmer Vernooij)
+
+* The version of bzr being run is now written to the log file.
+  (__monty__, #257170)
+
+* Transport network activity indicator is shown more of the time when
+  Bazaar is doing network IO.
+  (Martin Pool)
+
+Documentation
+*************
+
+* Add documentation on creating merges with more than one parent.
+  (Neil Martinsen-Burrell, #481526)
+
+* Better explain the --uncommitted option of merge.
+  (Neil Martinsen-Burrell, #505088)
+
+* Improve discussion of pending merges in the documentation for
+  ``revert``.  (Neil Martinsen-Burrell, #505093)
+
+* Improved help for ``bzr send``. 
+  (Martin Pool, Bojan Nikolic)
+
+* There is a System Administrator's Guide in ``doc/en/admin-guide``,
+  including discussions of installation, relevant plugins, security and 
+  backup. (Neil Martinsen-Burrell)
+
+* The ``conflicts`` help topic has been renamed to ``conflict-types``.
+  (Ian Clatworthy)
+
+* The User Reference is now presented as a series of topics.
+  Many of the included topics have link and format tweaks applied.
+  (Ian Clatworthy)
+
+API Changes
+***********
+
+* Added ``cachedproperty`` decorator to ``bzrlib.decorators``.
+  (Andrew Bennetts)
+
+* Many test features were renamed from ``FooFeature`` to ``foo_feature``
+  to be consistent with instances being lower case and classes being
+  CamelCase. For the features that were more likely to be used, we added a
+  deprecation thunk, but not all. (John Arbash Meinel)
+
+* Merger classes (such as ``Merge3Merger``) now expect a ``this_branch``
+  parameter in their constructors, and provide ``this_branch`` as an
+  attribute. (Andrew Bennetts)
+  
+* The Branch hooks pre_change_branch_tip no longer masks exceptions raised
+  by plugins - the original exceptions are now preserved. (Robert Collins)
+
+* The Transport ``Server.tearDown`` method is now renamed to
+  ``stop_server`` and ``setUp`` to ``start_server`` for consistency with
+  our normal naming pattern, and to avoid confusion with Python's
+  ``TestCase.tearDown``.  (Martin Pool)
+
+* ``WorkingTree.update`` implementations must now accept a ``revision``
+  parameter.
+
+Internals
+*********
+
+* Added ``BzrDir.open_branchV3`` smart server request, which can receive
+  a string of details (such as "location is a repository") as part of a
+  ``nobranch`` response.  (Andrew Bennetts, #440952)
+  
+* New helper osutils.UnicodeOrBytesToBytesWriter which encodes unicode
+  objects but passes str objects straight through. This is used for
+  selftest but may be useful for diff and other operations that generate
+  mixed output. (Robert Collins)
+
+* New exception ``NoRoundtrippingSupport``, for use by foreign branch 
+  plugins. (Jelmer Vernooij)
+
+Testing
+*******
+
+* ``bzrlib.tests.permute_for_extension`` is a helper that simplifies
+  running all tests in the current module, once against a pure python
+  implementation, and once against an extension (pyrex/C) implementation.
+  It can be used to dramatically simplify the implementation of
+  ``load_tests``.  (John Arbash Meinel)
+
+* ``bzrlib.tests.TestCase`` now subclasses ``testtools.testcase.TestCase``.
+  This permits features in testtools such as getUniqueInteger and
+  getUniqueString to be used. Because of this, testtools version 0.9.2 or
+  newer is now a dependency to run bzr selftest. Running with versions of
+  testtools less than 0.9.2 will cause bzr to error while loading the test
+  suite. (Robert Collins)
+
+* Shell-like tests now support the command "mv" for moving files.  The
+  syntax for ``mv file1 file2``, ``mv dir1 dir2`` and ``mv file dir`` is
+  supported.  (Neil Martinsen-Burrell)
+
+* The test progress bar no longer distinguishes tests that 'errored' from
+  tests that 'failed' - they're all just failures.
+  (Martin Pool)
+
+
 bzr 2.0.5 (not released yet)
 ############################
 
@@ -111,6 +453,190 @@
   bug #495023. (John Arbash Meinel)
 
 
+bzr 2.1.0b4
+###########
+
+:Codename: san francisco airport
+:2.1.0b4: 2009-12-14
+
+The fourth beta release in the 2.1 series brings with it a significant
+number of bugfixes (~20). The test suite is once again (finally) "green"
+on Windows, and should remain that way for future releases. There are a
+few performance related updates (faster upgrade and log), and several UI
+tweaks. There has also been a significant number of tweaks to the runtime
+documentation. 2.1.0b4 include everything from the 2.0.3 release.
+
+
+Compatibility Breaks
+********************
+
+* The BZR_SSH environmental variable may now be set to the path of a secure
+  shell client. If currently set to the value ``ssh`` it will now guess the
+  vendor of the program with that name, to restore the old behaviour that
+  indicated the SSH Corporation client use ``sshcorp`` instead as the magic
+  string. (Martin <[e-mail]>, #176292)
+
+New Features
+************
+
+* ``bzr commit`` now has a ``--commit-time`` option.
+  (Alexander Sack, #459276)
+
+* ``-Dhpss`` now increases logging done when run on the bzr server,
+  similarly to how it works on the client. (John Arbash Meinel)
+
+* New option ``bzr unshelve --keep`` applies the changes and leaves them
+  on the shelf.  (Martin Pool, Oscar Fuentes, #492091)
+
+* The ``BZR_COLUMNS`` envrionment variable can be set to force bzr to
+  respect a given terminal width. This can be useful when output is
+  redirected or in obscure cases where the default value is not
+  appropriate. Pagers can use it to get a better control of the line
+  lengths. 
+  (Vincent Ladeuil)
+
+* The new command ``bzr lp-mirror`` will request that Launchpad update its
+  mirror of a local branch. This command will only function if launchpadlib
+  is installed.
+  (Jonathan Lange)
+
+
+Bug Fixes
+*********
+
+* After renaming a file, the dirstate could accidentally reference
+  ``source\\path`` rather than ``source/path`` on Windows. This might be a
+  source of some dirstate-related failures. (John Arbash Meinel)
+
+* ``bzr commit`` now detects commit messages that looks like file names
+  and issues a warning.
+  (Gioele Barabucci, #73073)
+
+* ``bzr ignore /`` no longer causes an IndexError. (Gorder Tyler, #456036)
+
+* ``bzr log -n0 -rN`` should not return revisions beyond its merged revisions.
+  (#325618, #484109, Marius Kruger)
+
+* ``bzr merge --weave`` and ``--lca`` will now create ``.BASE`` files for
+  files with conflicts (similar to ``--merge3``). The contents of the file
+  is a synthesis of all bases used for the merge.
+  (John Arbash Meinel, #40412)
+
+* ``bzr mv --quiet`` really is quiet now.  (Gordon Tyler, #271790)
+
+* ``bzr serve`` is more clear about the risk of supplying --allow-writes.
+  (Robert Collins, #84659)
+
+* ``bzr serve --quiet`` really is quiet now.  (Gordon Tyler, #252834)
+
+* Fix bug with redirected URLs over authenticated HTTP.
+  (Glen Mailer, Neil Martinsen-Burrell, Vincent Ladeuil, #395714)
+
+* Interactive merge doesn't leave branch locks behind.  (Aaron Bentley)
+
+* Lots of bugfixes for the test suite on Windows. We should once again
+  have a test suite with no failures on Windows. (John Arbash Meinel)
+
+* ``osutils.terminal_width()`` obeys the BZR_COLUMNS environment
+  variable but returns None if the terminal is not a tty (when output is
+  redirected for example). Also fixes its usage under OSes that doesn't
+  provide termios.TIOCGWINSZ. Make sure the corresponding tests runs on
+  windows too.
+  (Joke de Buhr, Vincent Ladeuil, #353370, #62539)
+  (John Arbash Meinel, Vincent Ladeuil, #492561)
+
+* Terminate ssh subprocesses when no references to them remain, fixing
+  subprocess and file descriptor leaks.  (Andrew Bennetts, #426662)
+  
+* The ``--hardlink`` option of ``bzr branch`` and ``bzr checkout`` now
+  works for 2a format trees.  Only files unaffected by content filters
+  will be hardlinked.  (Andrew Bennetts, #408193)
+
+* The new glob expansion on Windows would replace all ``\`` characters
+  with ``/`` even if it there wasn't a glob to expand, the arg was quoted,
+  etc. Now only change slashes if there is something being glob expanded.
+  (John Arbash Meinel, #485771)
+
+* Use our faster ``KnownGraph.heads()`` functionality when computing the
+  new rich-root heads. This can cut a conversion time in half (mysql from
+  13.5h => 6.2h) (John Arbash Meinel, #487632)
+
+* When launching a external diff tool via bzr diff --using, temporary files
+  are no longer created, rather, the path to the file in the working tree is
+  passed to the external diff tool. This allows the file to be edited if the
+  diff tool provides for this. (Gary van der Merwe, #490738)
+  
+* The launchpad-open command can now be used from a subdirectory of a
+  branch, not just from the root of the branch. 
+  (Neil Martinsen-Burrell, #489102)
+
+
+Improvements
+************
+
+* ``bzr log`` is now faster. (Ian Clatworthy)
+
+* ``bzr update`` provides feedback on which branch it is up to date with.
+  (Neil Martinsen-Burrell)
+
+* ``bzr upgrade`` from pre-2a to 2a can be significantly faster (4x).
+  For details see the xml8 patch and heads() improvements.
+  (John Arbash Meinel)
+
+* ``bzrlib.urlutils.local_path_from_url`` now accepts
+  'file://localhost/' as well as 'file:///' URLs on POSIX.  (Michael
+  Hudson)
+
+* The progress bar now shows only a spinner and per-operation counts,
+  not an overall progress bar.  The previous bar was often not correlated
+  with real overall operation progress, either because the operations take
+  nonlinear time, or because at the start of the operation Bazaar couldn't
+  estimate how much work there was to do.  (Martin Pool)
+
+Documentation
+*************
+
+* Lots of documentation tweaks for inline help topics and command help
+  information.
+
+API Changes
+***********
+
+* ``bzrlib.textui`` (vestigial module) removed.  (Martin Pool)
+
+* The Launchpad plugin now has a function ``login`` which will log in to
+  Launchpad with launchpadlib, and ``load_branch`` which will return the
+  Launchpad Branch object corresponding to a given Bazaar Branch object.
+  (Jonathan Lange)
+
+Internals
+*********
+
+* New test Feature: ``ModuleAvailableFeature``. It is designed to make it
+  easier to handle what tests you want to run based on what modules can be
+  imported. (Rather than lots of custom-implemented features that were
+  basically copy-and-pasted.) (John Arbash Meinel)
+
+* ``osutils.timer_func()`` can be used to get either ``time.time()`` or
+  ``time.clock()`` when you want to do performance timing.
+  ``time.time()`` is limited to 15ms resolution on Windows, but
+  ``time.clock()`` gives CPU and not wall-clock time on other platforms.
+  (John Arbash Meinel)
+
+* Several code paths that were calling ``Transport.get().read()`` have
+  been changed to the equalivent ``Transport.get_bytes()``. The main
+  difference is that the latter will explicitly call ``file.close()``,
+  rather than expecting the garbage collector to handle it. This helps
+  with some race conditions on Windows during the test suite and sftp
+  tests. (John Arbash Meinel)
+
+Testing
+*******
+
+* TestCaseWithMemoryTransport no longer sets $HOME and $BZR_HOME to
+  unicode strings. (Michael Hudson, #464174)
+
+
 bzr 2.0.3
 #########
 
@@ -140,6 +666,233 @@
 * Improve "Binary files differ" hunk handling.  (Aaron Bentley, #436325)
 
 
+bzr 2.1.0b3
+###########
+
+:Codename: after sprint recovery
+:2.1.0b3: 2009-11-16
+
+This release was pushed up from its normal release cycle due to a
+regression in python 2.4 compatibility in 2.1.0b2.  Since this regression
+was caught before 2.1.0b2 was officially announced, the full changelog
+includes both 2.1.0b3 and 2.1.0b2 changes.
+
+Highlights of 2.1.0b3 are: new globbing code for all commands on Windows,
+the test suite now conforms to python's trunk enhanced semantics (skip,
+etc.), and ``bzr info -v`` will now report the correct branch and repo
+formats for Remote objects.
+
+
+New Features
+************
+
+* Users can define a shelve editor to provide shelf functionality at a
+  granularity finer than per-patch-hunk. (Aaron Bentley)
+
+Bug Fixes
+*********
+
+* Fix for shell completion and short options.  (Benoît PIERRE)
+
+* Hooks daughter classes should always call the base constructor.
+  (Alexander Belchenko, Vincent Ladeuil, #389648) 
+
+* Improve "Binary files differ" hunk handling.  (Aaron Bentley, #436325)
+
+* On Windows, do glob expansion at the command-line level (as is usually
+  done in bash, etc.) This means that *all* commands get glob expansion
+  (bzr status, bzr add, bzr mv, etc). It uses a custom command line
+  parser, which allows us to know if a given section was quoted. It means
+  you can now do ``bzr ignore "*.py"``.
+  (John Arbash Meinel, #425510, #426410, #194450)
+
+* Sanitize commit messages that come in from the '-m' flag. We translate
+  '\r\n' => '\n' and a plain '\r' => '\n'. The storage layer doesn't
+  allow those because XML store silently translate it anyway. (The parser
+  auto-translates \r\n => \n in ways that are hard for us to catch.)
+
+* Show correct branch and repository format descriptions in 
+  ``bzr info -v`` on a smart server location.  (Andrew Bennetts, #196080)
+
+* The fix for bug #186920 accidentally broke compatibility with python
+  2.4.  (Vincent Ladeuil, #475585)
+
+* Using ``Repository.get_commit_builder().record_iter_changes()`` now
+  correctly sets ``self.inv_sha1`` to a sha1 string and
+  ``self.new_inventory`` to an Inventory instance after calling
+  ``self.finish_inventory()``. (Previously it accidently set both values
+  as a tuple on ``self.inv_sha1``. This was missed because
+  ``repo.add_revision`` ignores the supplied inventory sha1 and recomputes
+  the sha1 from the repo directly. (John Arbash Meinel)
+
+* Shelve command refuse to run if there is no real terminal.
+  (Alexander Belchenko)
+
+* Avoid unnecessarily flushing of trace file; it's now unbuffered at the
+  Python level.  (Martin Pool)
+
+Documentation
+*************
+
+* Include Japanese translations for documentation (Inada Naoki)
+
+* New API ``ui_factory.make_output_stream`` to be used for sending bulk
+  (rather than user-interaction) data to stdout.  This automatically
+  coordinates with progress bars or other terminal activity, and can be
+  overridden by GUIs.
+  (Martin Pool, 493944)
+
+Internals
+*********
+
+* Some of the core groupcompress functionality now releases the GIL before
+  operation. Similar to how zlib and bz2 operate without the GIL in the
+  core compression and decompression routines. (John Arbash Meinel)
+
+Testing
+*******
+
+* -Dhpssvfs will now trigger on ``RemoteBzrDir._ensure_real``, providing
+  more debugging of VFS access triggers. (Robert Collins)
+
+* KnownFailure is now signalled to ``ExtendedTestResult`` using the same
+  method that Python 2.7 uses - ``addExpectedFailure``. (Robert Collins)
+
+* ``--parallel=fork`` is now compatible with --subunit.
+  (Robert Collins, Vincent Ladeuil, #419776)
+
+* Reporting of failures shows test ids not descriptions and thus shows
+  parameterised tests correctly. (Robert Collins)
+
+* TestNotApplicable is now handled within the TestCase.run method rather
+  than being looked for within ``ExtendedTestResult.addError``. This
+  provides better handling with other ``TestResult`` objects, degrading to
+  sucess rather than error. (Robert Collins)
+
+* The private method ``_testConcluded`` on ``ExtendedTestResult`` has been
+  removed - it was empty and unused. (Robert Collins)
+
+* UnavailableFeature is now handled within the TestCase.run method rather
+  than being looked for within addError. If the Result object does not
+  have an addNotSupported method, addSkip is attempted instead, and
+  failing that addSuccess. (Robert Collins)
+
+* When a TestResult does not have an addSkip method, skipped tests are now
+  reported as successful tests, rather than as errors. This change is
+  to make it possible to get a clean test run with a less capable
+  TestResult. (Robert Collins)
+
+
+
+bzr 2.1.0b2
+###########
+
+:Codename: a load off my mind
+:2.1.0b2: 2009-11-02
+
+This is our second feature-filled release since 2.0, pushing us down the
+path to a 2.1.0. Once again, all bugfixes in 2.0.2 are present in 2.1.0b2.
+
+Key highlights in this release are: improved handling of
+failures-during-cleanup for commit, fixing a long-standing bug with
+``bzr+http`` and shared repositories, all ``lp:`` urls to be resolved
+behind proxies, and a new StaticTuple datatype, allowing us to reduce
+memory consumption (50%) and garbage collector overhead (40% faster) for
+many operations.
+
+* A new ``--concurrency`` option has been added as well as an associated
+  BZR_CONCURRENCY environment variable to specify the number of
+  processes that can be run concurrently when running ``bzr selftest``. The
+  command-line option overrides the environment variable if both are
+  specified. If none is specified. the number of processes is obtained
+  from the OS as before.  (Matt Nordhoff, Vincent Ladeuil)
+
+Bug Fixes
+*********
+
+* ``bzr+http`` servers no longer give spurious jail break errors when
+  serving branches inside a shared repository.  (Andrew Bennetts, #348308)
+
+* Errors during commit are handled more robustly so that knock-on errors
+  are less likely to occur, and will not obscure the original error if
+  they do occur.  This fixes some causes of ``TooManyConcurrentRequests``
+  and similar errors.  (Andrew Bennetts, #429747, #243391)
+
+* Launchpad urls can now be resolved from behind proxies.
+  (Gordon Tyler, Vincent Ladeuil, #186920)
+
+* Reduce the strictness for StaticTuple, instead add a debug flag
+  ``-Dstatic_tuple`` which will change apis to be strict and raise errors.
+  This way, most users won't see failures, but developers can improve
+  internals. (John Arbash Meinel, #471193)
+
+* TreeTransform.adjust_path updates the limbo paths of descendants of adjusted
+  files.  (Aaron Bentley)
+
+* Unicode paths are now handled correctly and consistently by the smart
+  server.  (Andrew Bennetts, Michael Hudson, #458762)
+
+Improvements
+************
+
+* When reading index files, we now use a ``StaticTuple`` rather than a
+  plain ``tuple`` object. This generally gives a 20% decrease in peak
+  memory, and can give a performance boost up to 40% on large projects.
+  (John Arbash Meinel)
+
+* Peak memory under certain operations has been reduced significantly.
+  (eg, 'bzr branch launchpad standalone' is cut in half)
+  (John Arbash Meinel)
+
+Documentation
+*************
+
+* Filtered views user documentation upgraded to refer to format 2a
+  instead of pre-2.0 formats. (Ian Clatworthy)
+
+API Changes
+***********
+
+* Remove deprecated ``CLIUIFactory``.  (Martin Pool)
+
+* ``UIFactory`` now has new ``show_error``, ``show_message`` and
+  ``show_warning`` methods, which can be hooked by non-text UIs.  
+  (Martin Pool)
+
+Internals
+*********
+
+* Added ``bzrlib._simple_set_pyx``. This is a hybrid between a Set and a
+  Dict (it only holds keys, but you can lookup the object located at a
+  given key). It has significantly reduced memory consumption versus the
+  builtin objects (1/2 the size of Set, 1/3rd the size of Dict). This is
+  used as the interning structure for StaticTuple objects.
+  (John Arbash Meinel)
+
+* ``bzrlib._static_tuple_c.StaticTuple`` is now available and used by
+  the btree index parser and the chk map parser. This class functions
+  similarly to ``tuple`` objects. However, it can only point to a limited
+  collection of types.  (Currently StaticTuple, str, unicode, None, bool,
+  int, long, float, but not subclasses).  This allows us to remove it from
+  the garbage collector (it cannot be in a cycle), it also allows us to
+  intern the objects. In testing, this can reduce peak memory by 20-40%,
+  and significantly improve performance by removing objects from being
+  inspected by the garbage collector.  (John Arbash Meinel)
+
+* ``GroupCompressBlock._ensure_content()`` will now release the
+  ``zlib.decompressobj()`` when the first request is for all of the
+  content. (Previously it would only be released if you made a request for
+  part of the content, and then all of it later.) This turns out to be a
+  significant memory savings, as a ``zstream`` carries around approx 260kB
+  of internal state and buffers. (For branching bzr.dev this drops peak
+  memory from 382MB => 345MB.) (John Arbash Meinel)
+
+* When streaming content between ``2a`` format repositories, we now clear
+  caches from earlier versioned files. (So 'revisions' is cleared when we
+  start reading 'inventories', etc.) This can have a significant impact on
+  peak memory for initial copies (~200MB). (John Arbash Meinel)
+
+
 bzr 2.0.2
 #########
 
@@ -187,6 +940,219 @@
   instead of pre-2.0 formats. (Ian Clatworthy)
 
 
+bzr 2.1.0b1
+###########
+
+:Codename: While the cat is away
+:2.1.0b1: 2009-10-14
+
+This is the first development release in the new split "stable" and
+"development" series. As such, the release is a snapshot of bzr.dev
+without creating a release candidate first. This release includes a
+fair amount of internal changes, with deprecated code being removed,
+and several new feature developments. People looking for a stable code
+base with only bugfixes should focus on the 2.0.1 release. All bugfixes
+present in 2.0.1 are present in 2.1.0b1.
+
+Highlights include support for ``bzr+ssh://host/~/homedir`` style urls,
+finer control over the plugin search path via extended BZR_PLUGIN_PATH
+syntax, visible warnings when extension modules fail to load, and improved
+error handling during unlocking.
+
+
+New Features
+************
+
+* Bazaar can now send mail through Apple OS X Mail.app. 
+  (Brian de Alwis)
+
+* ``bzr+ssh`` and ``bzr`` paths can now be relative to home directories
+  specified in the URL.  Paths starting with a path segment of ``~`` are
+  relative to the home directory of the user running the server, and paths
+  starting with ``~user`` are relative to the home directory of the named
+  user.  For example, for a user "bob" with a home directory of
+  ``/home/bob``, these URLs are all equivalent:
+
+  * ``bzr+ssh://bob@host/~/repo``
+  * ``bzr+ssh://bob@host/~bob/repo``
+  * ``bzr+ssh://bob@host/home/bob/repo``
+
+  If ``bzr serve`` was invoked with a ``--directory`` argument, then no
+  home directories outside that directory will be accessible via this
+  method.
+
+  This is a feature of ``bzr serve``, so pre-2.1 clients will
+  automatically benefit from this feature when ``bzr`` on the server is
+  upgraded.  (Andrew Bennetts, #109143)
+
+* Extensions can now be compiled if either Cython or Pyrex is available.
+  Currently Pyrex is preferred, but that may change in the future.
+  (Arkanes)
+
+* Give more control on BZR_PLUGIN_PATH by providing a way to refer to or
+  disable the user, site and core plugin directories.
+  (Vincent Ladeuil, #412930, #316192, #145612)
+
+Bug Fixes
+*********
+
+* Bazaar's native protocol code now correctly handles EINTR, which most
+  noticeably occurs if you break in to the debugger while connected to a
+  bzr+ssh server.  You can now can continue from the debugger (by typing
+  'c') and the process continues.  However, note that pressing C-\ in the
+  shell may still kill the SSH process, which is bug 162509, so you must
+  sent a signal to the bzr process specifically, for example by typing
+  ``kill -QUIT PID`` in another shell.  (Martin Pool, #341535)
+
+* ``bzr add`` in a tree that has files with ``\r`` or ``\n`` in the
+  filename will issue a warning and skip over those files.
+  (Robert Collins, #3918)
+
+* ``bzr dpush`` now aborts if uncommitted changes (including pending merges)
+  are present in the working tree. The configuration option ``dpush_strict``
+  can be used to set the default for this behavior.
+  (Vincent Ladeuil, #438158)
+
+* ``bzr merge`` and ``bzr remove-tree`` now requires --force if pending
+  merges are present in the working tree.
+  (Vincent Ladeuil, #426344)
+
+* Clearer message when Bazaar runs out of memory, instead of a ``MemoryError``
+  traceback.  (Martin Pool, #109115)
+
+* Don't give a warning on Windows when failing to import ``_readdir_pyx``
+  as it is never built. (John Arbash Meinel, #430645)
+
+* Don't restrict the command name used to run the test suite.
+  (Vincent Ladeuil, #419950)
+
+* ftp transports were built differently when the kerberos python module was
+  present leading to obscure failures related to ASCII/BINARY modes.
+  (Vincent Ladeuil, #443041)
+
+* Network streams now decode adjacent records of the same type into a
+  single stream, reducing layering churn. (Robert Collins)
+
+* PreviewTree behaves correctly when get_file_mtime is invoked on an unmodified
+  file. (Aaron Bentley, #251532)
+
+* Registry objects should not use iteritems() when asked to use items().
+  (Vincent Ladeuil, #430510)
+
+* Weave based repositories couldn't be cloned when committers were using
+  domains or user ids embedding '.sig'. Now they can.
+  (Matthew Fuller, Vincent Ladeuil, #430868)
+
+Improvements
+************
+
+* Revision specifiers can now be given in a more DWIM form, without
+  needing explicit prefixes for specifiers like tags or revision id's.
+  See ``bzr help revisionspec`` for full details.  (Matthew Fuller)
+
+* Bazaar gives a warning before exiting, and writes into ``.bzr.log``, if 
+  compiled extensions can't be loaded.  This typically indicates a
+  packaging or installation problem.  In this case Bazaar will keep
+  running using pure-Python versions, but this may be substantially
+  slower.  The warning can be disabled by setting
+  ``ignore_missing_extensions = True`` in ``bazaar.conf``.
+  See also <https://answers.launchpad.net/bzr/+faq/703>.
+  (Martin Pool, #406113, #430529)
+
+* Secondary errors that occur during Branch.unlock and Repository.unlock
+  no longer obscure the original error.  These methods now use a new
+  decorator, ``only_raises``.  This fixes many causes of
+  ``TooManyConcurrentRequests`` and similar errors.
+  (Andrew Bennetts, #429747)
+
+Documentation
+*************
+
+* Describe the new shell-like test feature. (Vincent Ladeuil)
+
+* Help on hooks no longer says 'Not deprecated' for hooks that are
+  currently supported. (Ian Clatworthy, #422415)
+
+API Changes
+***********
+
+* ``bzrlib.user_encoding`` has been removed; use
+  ``bzrlib.osutils.get_user_encoding`` instead.  (Martin Pool)
+
+* ``bzrlib.tests`` now uses ``stopTestRun`` for its ``TestResult``
+  subclasses - the same as python's unittest module. (Robert Collins)
+  
+* ``diff._get_trees_to_diff`` has been renamed to 
+  ``diff.get_trees_and_branches_to_diff``. It is now a public API, and it 
+  returns the old and new branches. (Gary van der Merwe)
+
+* ``bzrlib.trace.log_error``, ``error`` and ``info`` have been deprecated.
+  (Martin Pool)
+
+* ``MutableTree.has_changes()`` does not require a tree parameter anymore. It
+  now defaults to comparing to the basis tree. It now checks for pending
+  merges too.  ``Merger.check_basis`` has been deprecated and replaced by the
+  corresponding has_changes() calls. ``Merge.compare_basis``,
+  ``Merger.file_revisions`` and ``Merger.ensure_revision_trees`` have also
+  been deprecated.
+  (Vincent Ladeuil, #440631)
+
+* ``ProgressTask.note`` is deprecated.
+  (Martin Pool)
+
+Internals
+*********
+
+* Added ``-Drelock`` debug flag.  It will ``note`` a message every time a
+  repository or branch object is unlocked then relocked the same way.
+  (Andrew Bennetts)
+  
+* ``BTreeLeafParser.extract_key`` has been tweaked slightly to reduce
+  mallocs while parsing the index (approx 3=>1 mallocs per key read).
+  This results in a 10% speedup while reading an index.
+  (John Arbash Meinel)
+
+* The ``bzrlib.lsprof`` module has a new class ``BzrProfiler`` which makes
+  profiling in some situations like callbacks and generators easier.
+  (Robert Collins)
+
+Testing
+*******
+
+* Passing ``--lsprof-tests -v`` to bzr selftest will cause lsprof output to
+  be output for every test. Note that this is very verbose! (Robert Collins)
+
+* Setting ``BZR_TEST_PDB=1`` when running selftest will cause a pdb
+  post_mortem to be triggered when a test failure occurs. (Robert Collins)
+
+* Shell-like tests can now be written. Code in ``bzrlib/tests/script.py`` ,
+  documentation in ``developers/testing.txt`` for details.
+  (Vincent Ladeuil)
+
+* Some tests could end up with the same id, that was dormant for
+  a long time.
+  (Vincent Ladeuil, #442980)
+
+* Stop showing the number of tests due to missing features in the test
+  progress bar.  (Martin Pool)
+
+* Test parameterisation now does a shallow copy, not a deep copy of the test
+  to be parameterised. This is not expected to break external use of test
+  parameterisation, and is substantially faster. (Robert Collins)
+
+* Tests that try to open a bzr dir on an arbitrary transport will now
+  fail unless they have explicitly permitted the transport via
+  ``self.permit_url``. The standard test factories such as ``self.get_url``
+  will permit the urls they provide automatically, so only exceptional
+  tests should need to do this. (Robert Collins)
+
+* The break-in test no longer cares about clean shutdown of the child,
+  instead it is happy if the debugger starts up. (Robert  Collins)
+
+* The full test suite is expected to pass when the C extensions are not
+  present. (Vincent Ladeuil, #430749)
+
+
 bzr 2.0.1
 #########
 
@@ -290,6 +1256,7 @@
   to "land in 2.0.0". (Changes how bzrlib._format_version_tuple() handles
   micro = 0.) (John Arbash Meinel)
 
+
 bzr 2.0.0rc2
 ############
 
@@ -346,10 +1313,6 @@
   ghosts in its mainline.  (Evaluating None as a tuple is bad.)
   (John Arbash Meinel, #419241)
 
-* Fix a segmentation fault when computing the ``merge_sort`` of a graph
-  that has a ghost in the mainline ancestry.
-  (John Arbash Meinel, #419241)
-
 * ``groupcompress`` sort order is now more stable, rather than relying on
   ``topo_sort`` ordering. The implementation is now
   ``KnownGraph.gc_sort``. (John Arbash Meinel)
@@ -417,6 +1380,9 @@
 Bug Fixes
 *********
 
+* Further tweaks to handling of ``bzr add`` messages about ignored files.
+  (Jason Spashett, #76616)
+
 * Fetches were being requested in 'groupcompress' order, but weren't
   recombining the groups. Thus they would 'fragment' to get the correct
   order, but not 'recombine' to actually benefit from it. Until we get
@@ -462,7 +1428,7 @@
 * ``bzr shelve`` and ``bzr unshelve`` now work on windows.
   (Robert Collins, #305006)
 
-* Commit of specific files no longer prevents using the the iter_changes
+* Commit of specific files no longer prevents using the iter_changes
   codepath. On 2a repositories, commit of specific files should now be as
   fast, or slightly faster, than a full commit. (Robert Collins)
 
@@ -486,9 +1452,6 @@
   classes changed to manage lock lifetime of the trees they open in a way
   consistent with reader-exclusive locks. (Robert Collins, #305006)
 
-Internals
-*********
-
 Testing
 *******
 
@@ -535,6 +1498,9 @@
   a tree with content filtering where the size of the canonical form
   cannot be cheaply determined.  (Martin Pool)
 
+* When manually creating transport servers in test cases, a new helper
+  ``TestCase.start_server`` that registers a cleanup and starts the server
+  should be used. (Robert Collins)
 
 bzr 1.18
 ########
@@ -872,6 +1838,17 @@
   ``countTestsCases``. (Robert Collins)
 
 
+bzr 1.17.1 (unreleased)
+#######################
+
+Bug Fixes
+*********
+
+* The optional ``_knit_load_data_pyx`` C extension was never being
+  imported.  This caused significant slowdowns when reading data from
+  knit format repositories.  (Andrew Bennetts, #405653)
+  
+
 bzr 1.17
 ########
 :Codename: so-late-its-brunch
@@ -1220,7 +2197,7 @@
 ************
 
 * A new repository format ``2a`` has been added.  This is a beta release
-  of the the brisbane-core (aka group-compress) project.  This format now
+  of the brisbane-core (aka group-compress) project.  This format now
   suitable for wider testing by advanced users willing to deal with some
   bugs.  We would appreciate test reports, either positive or negative.
   Format 2a is substantially smaller and faster for many operations on
@@ -1372,6 +2349,9 @@
 Testing
 *******
 
+* ``make check`` no longer repeats the test run in ``LANG=C``.
+  (Martin Pool, #386180)
+
 * The number of cores is now correctly detected on OSX. (John Szakmeister)
 
 * The number of cores is also detected on Solaris and win32. (Vincent Ladeuil)
@@ -1946,7 +2926,7 @@
 
 * Added ``bzrlib.inventory_delta`` module.  This will be used for
   serializing and deserializing inventory deltas for more efficient
-  streaming on the the network.  (Robert Collins, Andrew Bennetts)
+  streaming on the network.  (Robert Collins, Andrew Bennetts)
 
 * ``Branch._get_config`` has been added, which splits out access to the
   specific config file from the branch. This is used to let RemoteBranch
@@ -2141,7 +3121,7 @@
 * Multiple authors for a commit can now be recorded by using the "--author"
   option multiple times. (James Westby, #185772)
 
-* New clean-tree command, from bzrtools.  (Aaron Bentley, Jelmer Vernoij)
+* New clean-tree command, from bzrtools.  (Aaron Bentley, Jelmer Vernooij)
 
 * New command ``bzr launchpad-open`` opens a Launchpad web page for that
   branch in your web browser, as long as the branch is on Launchpad at all.
@@ -4670,7 +5650,7 @@
   exception. (Andrew Bennetts)
 
 * New ``--debugflag``/``-E`` option to ``bzr selftest`` for setting
-  options for debugging tests, these are complementary to the the -D
+  options for debugging tests, these are complementary to the -D
   options.  The ``-Dselftest_debug`` global option has been replaced by the
   ``-E=allow_debug`` option for selftest. (Andrew Bennetts)
 
@@ -5425,7 +6405,7 @@
   checkouts.  (Aaron Bentley, #182040)
 
 * Stop polluting /tmp when running selftest.
-  (Vincent Ladeuil, #123623)
+  (Vincent Ladeuil, #123363)
 
 * Switch from NFKC => NFC for normalization checks. NFC allows a few
   more characters which should be considered valid.

=== modified file 'bzr'
--- bzr	2009-12-15 16:56:18 +0000
+++ bzr	2010-02-18 00:00:51 +0000
@@ -23,7 +23,7 @@
 import warnings
 
 # update this on each release
-_script_version = (2, 0, 4)
+_script_version = (2, 1, 1)
 
 if __doc__ is None:
     print "bzr does not support python -OO."

=== modified file 'bzrlib/__init__.py'
--- bzrlib/__init__.py	2010-01-21 19:35:57 +0000
+++ bzrlib/__init__.py	2010-02-18 00:00:52 +0000
@@ -31,16 +31,10 @@
     import bzrlib.lazy_regex
     bzrlib.lazy_regex.install_lazy_compile()
 
-from bzrlib.osutils import get_user_encoding
-
 
 IGNORE_FILENAME = ".bzrignore"
 
 
-# XXX: Deprecated as of bzr-1.17 use osutils.get_user_encoding() directly
-user_encoding = get_user_encoding()
-
-
 __copyright__ = "Copyright 2005, 2006, 2007, 2008, 2009 Canonical Ltd."
 
 # same format as sys.version_info: "A tuple containing the five components of
@@ -50,10 +44,11 @@
 # Python version 2.0 is (2, 0, 0, 'final', 0)."  Additionally we use a
 # releaselevel of 'dev' for unreleased under-development code.
 
-version_info = (2, 0, 4, 'final', 0)
+version_info = (2, 1, 1, 'dev', 0)
 
 # API compatibility version: bzrlib is currently API compatible with 1.15.
-api_minimum_version = (1, 17, 0)
+api_minimum_version = (2, 1, 0)
+
 
 def _format_version_tuple(version_info):
     """Turn a version number 2, 3 or 5-tuple into a short string.

=== modified file 'bzrlib/_annotator_pyx.pyx'
--- bzrlib/_annotator_pyx.pyx	2010-01-05 04:59:57 +0000
+++ bzrlib/_annotator_pyx.pyx	2010-02-18 00:00:52 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2009 Canonical Ltd
+# Copyright (C) 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by

=== modified file 'bzrlib/_bencode_pyx.pyx'
--- bzrlib/_bencode_pyx.pyx	2009-12-18 21:58:32 +0000
+++ bzrlib/_bencode_pyx.pyx	2010-02-18 00:00:52 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2007,2009 Canonical Ltd
+# Copyright (C) 2007, 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -58,6 +58,13 @@
     void D_UPDATE_TAIL(Decoder, int n)
     void E_UPDATE_TAIL(Encoder, int n)
 
+# To maintain compatibility with older versions of pyrex, we have to use the
+# relative import here, rather than 'bzrlib._static_tuple_c'
+from _static_tuple_c cimport StaticTuple, StaticTuple_CheckExact, \
+    import_static_tuple_c
+
+import_static_tuple_c()
+
 
 cdef class Decoder:
     """Bencode decoder"""
@@ -371,7 +378,8 @@
                 self._encode_int(x)
             elif PyLong_CheckExact(x):
                 self._encode_long(x)
-            elif PyList_CheckExact(x) or PyTuple_CheckExact(x):
+            elif (PyList_CheckExact(x) or PyTuple_CheckExact(x)
+                  or StaticTuple_CheckExact(x)):
                 self._encode_list(x)
             elif PyDict_CheckExact(x):
                 self._encode_dict(x)

=== modified file 'bzrlib/_btree_serializer_py.py'
--- bzrlib/_btree_serializer_py.py	2009-03-23 14:59:43 +0000
+++ bzrlib/_btree_serializer_py.py	2010-02-18 00:00:50 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2008 Canonical Ltd
+# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -17,27 +17,33 @@
 
 """B+Tree index parsing."""
 
+from bzrlib import static_tuple
+
+
 def _parse_leaf_lines(bytes, key_length, ref_list_length):
     lines = bytes.split('\n')
     nodes = []
+    as_st = static_tuple.StaticTuple.from_sequence
+    stuple = static_tuple.StaticTuple
     for line in lines[1:]:
         if line == '':
             return nodes
         elements = line.split('\0', key_length)
         # keys are tuples
-        key = tuple(elements[:key_length])
+        key = as_st(elements[:key_length]).intern()
         line = elements[-1]
         references, value = line.rsplit('\0', 1)
         if ref_list_length:
             ref_lists = []
             for ref_string in references.split('\t'):
-                ref_lists.append(tuple([
-                    tuple(ref.split('\0')) for ref in ref_string.split('\r') if ref
-                    ]))
-            ref_lists = tuple(ref_lists)
-            node_value = (value, ref_lists)
+                ref_list = as_st([as_st(ref.split('\0')).intern()
+                                  for ref in ref_string.split('\r') if ref])
+                ref_lists.append(ref_list)
+            ref_lists = as_st(ref_lists)
+            node_value = stuple(value, ref_lists)
         else:
-            node_value = (value, ())
+            node_value = stuple(value, stuple())
+        # No need for StaticTuple here as it is put into a dict
         nodes.append((key, node_value))
     return nodes
 

=== modified file 'bzrlib/_btree_serializer_pyx.pyx'
--- bzrlib/_btree_serializer_pyx.pyx	2010-01-05 04:59:57 +0000
+++ bzrlib/_btree_serializer_pyx.pyx	2010-02-18 00:00:52 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2008, 2009 Canonical Ltd
+# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -38,11 +38,16 @@
     Py_ssize_t PyString_Size(object p)
     Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *)
     char * PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *)
+    char * PyString_AS_STRING(object)
+    Py_ssize_t PyString_GET_SIZE(object)
     int PyString_AsStringAndSize_ptr(PyObject *, char **buf, Py_ssize_t *len)
     void PyString_InternInPlace(PyObject **)
     int PyTuple_CheckExact(object t)
+    object PyTuple_New(Py_ssize_t n_entries)
+    void PyTuple_SET_ITEM(object, Py_ssize_t offset, object) # steals the ref
     Py_ssize_t PyTuple_GET_SIZE(object t)
     PyObject *PyTuple_GET_ITEM_ptr_object "PyTuple_GET_ITEM" (object tpl, int index)
+    void Py_INCREF(object)
     void Py_DECREF_ptr "Py_DECREF" (PyObject *)
 
 cdef extern from "string.h":
@@ -52,6 +57,12 @@
     # void *memrchr(void *s, int c, size_t n)
     int strncmp(char *s1, char *s2, size_t n)
 
+# It seems we need to import the definitions so that the pyrex compiler has
+# local names to access them.
+from _static_tuple_c cimport StaticTuple, \
+    import_static_tuple_c, StaticTuple_New, \
+    StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact
+
 
 # TODO: Find some way to import this from _dirstate_helpers
 cdef void* _my_memrchr(void *s, int c, size_t n): # cannot_raise
@@ -68,6 +79,7 @@
         pos = pos - 1
     return NULL
 
+
 # TODO: Import this from _dirstate_helpers when it is merged
 cdef object safe_string_from_size(char *s, Py_ssize_t size):
     if size < 0:
@@ -91,6 +103,10 @@
     Py_DECREF_ptr(py_str)
     return result
 
+from bzrlib import _static_tuple_c
+# This sets up the StaticTuple C_API functionality
+import_static_tuple_c()
+
 
 cdef class BTreeLeafParser:
     """Parse the leaf nodes of a BTree index.
@@ -130,6 +146,7 @@
         self._cur_str = NULL
         self._end_str = NULL
         self._header_found = 0
+        # keys are tuples
 
     cdef extract_key(self, char * last):
         """Extract a key.
@@ -139,15 +156,14 @@
         """
         cdef char *temp_ptr
         cdef int loop_counter
-        # keys are tuples
-        loop_counter = 0
-        key_segments = []
-        while loop_counter < self.key_length:
-            loop_counter = loop_counter + 1
+        cdef StaticTuple key
+
+        key = StaticTuple_New(self.key_length)
+        for loop_counter from 0 <= loop_counter < self.key_length:
             # grab a key segment
             temp_ptr = <char*>memchr(self._start, c'\0', last - self._start)
             if temp_ptr == NULL:
-                if loop_counter == self.key_length:
+                if loop_counter + 1 == self.key_length:
                     # capture to last
                     temp_ptr = last
                 else:
@@ -157,15 +173,20 @@
                                                    last - self._start)))
                     raise AssertionError(failure_string)
             # capture the key string
-            # TODO: Consider using PyIntern_FromString, the only caveat is that
-            # it assumes a NULL-terminated string, so we have to check if
-            # temp_ptr[0] == c'\0' or some other char.
-            key_element = safe_interned_string_from_size(self._start,
+            if (self.key_length == 1
+                and (temp_ptr - self._start) == 45
+                and strncmp(self._start, 'sha1:', 5) == 0):
+                key_element = safe_string_from_size(self._start,
+                                                    temp_ptr - self._start)
+            else:
+                key_element = safe_interned_string_from_size(self._start,
                                                          temp_ptr - self._start)
             # advance our pointer
             self._start = temp_ptr + 1
-            PyList_Append(key_segments, key_element)
-        return tuple(key_segments)
+            Py_INCREF(key_element)
+            StaticTuple_SET_ITEM(key, loop_counter, key_element)
+        key = StaticTuple_Intern(key)
+        return key
 
     cdef int process_line(self) except -1:
         """Process a line in the bytes."""
@@ -174,6 +195,7 @@
         cdef char *ref_ptr
         cdef char *next_start
         cdef int loop_counter
+        cdef Py_ssize_t str_len
 
         self._start = self._cur_str
         # Find the next newline
@@ -209,12 +231,25 @@
             # Invalid line
             raise AssertionError("Failed to find the value area")
         else:
-            # capture the value string
-            value = safe_string_from_size(temp_ptr + 1, last - temp_ptr - 1)
+            # Because of how conversions were done, we ended up with *lots* of
+            # values that are identical. These are all of the 0-length nodes
+            # that are referred to by the TREE_ROOT (and likely some other
+            # directory nodes.) For example, bzr has 25k references to
+            # something like '12607215 328306 0 0', which ends up consuming 1MB
+            # of memory, just for those strings.
+            str_len = last - temp_ptr - 1
+            if (str_len > 4
+                and strncmp(" 0 0", last - 4, 4) == 0):
+                # This drops peak mem for bzr.dev from 87.4MB => 86.2MB
+                # For Launchpad 236MB => 232MB
+                value = safe_interned_string_from_size(temp_ptr + 1, str_len)
+            else:
+                value = safe_string_from_size(temp_ptr + 1, str_len)
             # shrink the references end point
             last = temp_ptr
+
         if self.ref_list_length:
-            ref_lists = []
+            ref_lists = StaticTuple_New(self.ref_list_length)
             loop_counter = 0
             while loop_counter < self.ref_list_length:
                 ref_list = []
@@ -246,18 +281,20 @@
                     if temp_ptr == NULL:
                         # key runs to the end
                         temp_ptr = ref_ptr
+
                     PyList_Append(ref_list, self.extract_key(temp_ptr))
-                PyList_Append(ref_lists, tuple(ref_list))
+                ref_list = StaticTuple_Intern(StaticTuple(*ref_list))
+                Py_INCREF(ref_list)
+                StaticTuple_SET_ITEM(ref_lists, loop_counter - 1, ref_list)
                 # prepare for the next reference list
                 self._start = next_start
-            ref_lists = tuple(ref_lists)
-            node_value = (value, ref_lists)
+            node_value = StaticTuple(value, ref_lists)
         else:
             if last != self._start:
                 # unexpected reference data present
                 raise AssertionError("unexpected reference data present")
-            node_value = (value, ())
-        PyList_Append(self.keys, (key, node_value))
+            node_value = StaticTuple(value, StaticTuple())
+        PyList_Append(self.keys, StaticTuple(key, node_value))
         return 0
 
     def parse(self):
@@ -292,7 +329,6 @@
     cdef Py_ssize_t flat_len
     cdef Py_ssize_t key_len
     cdef Py_ssize_t node_len
-    cdef PyObject * val
     cdef char * value
     cdef Py_ssize_t value_len
     cdef char * out
@@ -301,13 +337,12 @@
     cdef int first_ref_list
     cdef int first_reference
     cdef int i
-    cdef PyObject *ref_bit
     cdef Py_ssize_t ref_bit_len
 
-    if not PyTuple_CheckExact(node):
-        raise TypeError('We expected a tuple() for node not: %s'
+    if not PyTuple_CheckExact(node) and not StaticTuple_CheckExact(node):
+        raise TypeError('We expected a tuple() or StaticTuple() for node not: %s'
             % type(node))
-    node_len = PyTuple_GET_SIZE(node)
+    node_len = len(node)
     have_reference_lists = reference_lists
     if have_reference_lists:
         if node_len != 4:
@@ -316,8 +351,17 @@
     elif node_len < 3:
         raise ValueError('Without ref_lists, we need at least 3 entries not: %s'
             % len(node))
-    # I don't expect that we can do faster than string.join()
-    string_key = '\0'.join(<object>PyTuple_GET_ITEM_ptr_object(node, 1))
+    # TODO: We can probably do better than string.join(), namely
+    #       when key has only 1 item, we can just grab that string
+    #       And when there are 2 items, we could do a single malloc + len() + 1
+    #       also, doing .join() requires a PyObject_GetAttrString call, which
+    #       we could also avoid.
+    # TODO: Note that pyrex 0.9.6 generates fairly crummy code here, using the
+    #       python object interface, versus 0.9.8+ which uses a helper that
+    #       checks if this supports the sequence interface.
+    #       We *could* do more work on our own, and grab the actual items
+    #       lists. For now, just ask people to use a better compiler. :)
+    string_key = '\0'.join(node[1])
 
     # TODO: instead of using string joins, precompute the final string length,
     #       and then malloc a single string and copy everything in.
@@ -334,7 +378,7 @@
     refs_len = 0
     if have_reference_lists:
         # Figure out how many bytes it will take to store the references
-        ref_lists = <object>PyTuple_GET_ITEM_ptr_object(node, 3)
+        ref_lists = node[3]
         next_len = len(ref_lists) # TODO: use a Py function
         if next_len > 0:
             # If there are no nodes, we don't need to do any work
@@ -348,31 +392,31 @@
                     # references
                     refs_len = refs_len + (next_len - 1)
                     for reference in ref_list:
-                        if not PyTuple_CheckExact(reference):
+                        if (not PyTuple_CheckExact(reference)
+                            and not StaticTuple_CheckExact(reference)):
                             raise TypeError(
                                 'We expect references to be tuples not: %s'
                                 % type(reference))
-                        next_len = PyTuple_GET_SIZE(reference)
+                        next_len = len(reference)
                         if next_len > 0:
                             # We will need (len - 1) '\x00' characters to
                             # separate the reference key
                             refs_len = refs_len + (next_len - 1)
-                            for i from 0 <= i < next_len:
-                                ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
-                                if not PyString_CheckExact_ptr(ref_bit):
+                            for ref_bit in reference:
+                                if not PyString_CheckExact(ref_bit):
                                     raise TypeError('We expect reference bits'
                                         ' to be strings not: %s'
                                         % type(<object>ref_bit))
-                                refs_len = refs_len + PyString_GET_SIZE_ptr(ref_bit)
+                                refs_len = refs_len + PyString_GET_SIZE(ref_bit)
 
     # So we have the (key NULL refs NULL value LF)
     key_len = PyString_Size(string_key)
-    val = PyTuple_GET_ITEM_ptr_object(node, 2)
-    if not PyString_CheckExact_ptr(val):
+    val = node[2]
+    if not PyString_CheckExact(val):
         raise TypeError('Expected a plain str for value not: %s'
-                        % type(<object>val))
-    value = PyString_AS_STRING_ptr(val)
-    value_len = PyString_GET_SIZE_ptr(val)
+                        % type(val))
+    value = PyString_AS_STRING(val)
+    value_len = PyString_GET_SIZE(val)
     flat_len = (key_len + 1 + refs_len + 1 + value_len + 1)
     line = PyString_FromStringAndSize(NULL, flat_len)
     # Get a pointer to the new buffer
@@ -394,14 +438,14 @@
                     out[0] = c'\r'
                     out = out + 1
                 first_reference = 0
-                next_len = PyTuple_GET_SIZE(reference)
+                next_len = len(reference)
                 for i from 0 <= i < next_len:
                     if i != 0:
                         out[0] = c'\x00'
                         out = out + 1
-                    ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
-                    ref_bit_len = PyString_GET_SIZE_ptr(ref_bit)
-                    memcpy(out, PyString_AS_STRING_ptr(ref_bit), ref_bit_len)
+                    ref_bit = reference[i]
+                    ref_bit_len = PyString_GET_SIZE(ref_bit)
+                    memcpy(out, PyString_AS_STRING(ref_bit), ref_bit_len)
                     out = out + ref_bit_len
     out[0] = c'\0'
     out = out  + 1

=== modified file 'bzrlib/_chk_map_py.py'
--- bzrlib/_chk_map_py.py	2009-04-09 20:23:07 +0000
+++ bzrlib/_chk_map_py.py	2010-02-18 00:00:52 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2009 Canonical Ltd
+# Copyright (C) 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -19,6 +19,8 @@
 import zlib
 import struct
 
+from bzrlib.static_tuple import StaticTuple
+
 _LeafNode = None
 _InternalNode = None
 _unknown = None
@@ -93,7 +95,7 @@
         value_lines = lines[pos:pos+num_value_lines]
         pos += num_value_lines
         value = '\n'.join(value_lines)
-        items[tuple(elements[:-1])] = value
+        items[StaticTuple.from_sequence(elements[:-1])] = value
     if len(items) != length:
         raise AssertionError("item count (%d) mismatch for key %s,"
             " bytes %r" % (length, key, bytes))
@@ -141,7 +143,7 @@
     for line in lines[5:]:
         line = common_prefix + line
         prefix, flat_key = line.rsplit('\x00', 1)
-        items[prefix] = (flat_key,)
+        items[prefix] = StaticTuple(flat_key,)
     if len(items) == 0:
         raise AssertionError("We didn't find any item for %s" % key)
     result._items = items
@@ -155,4 +157,3 @@
     result._node_width = len(prefix)
     result._search_prefix = common_prefix
     return result
-

=== modified file 'bzrlib/_chk_map_pyx.pyx'
--- bzrlib/_chk_map_pyx.pyx	2010-01-05 04:59:57 +0000
+++ bzrlib/_chk_map_pyx.pyx	2010-02-18 00:00:51 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2009 Canonical Ltd
+# Copyright (C) 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -29,9 +29,8 @@
 
 cdef extern from "Python.h":
     ctypedef int Py_ssize_t # Required for older pyrex versions
-    struct _PyObject:
+    ctypedef struct PyObject:
         pass
-    ctypedef _PyObject PyObject
     int PyTuple_CheckExact(object p)
     Py_ssize_t PyTuple_GET_SIZE(object t)
     int PyString_CheckExact(object)
@@ -52,6 +51,18 @@
     char *PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *s)
     object PyString_FromStringAndSize(char*, Py_ssize_t)
 
+# cimport all of the definitions we will need to access
+from _static_tuple_c cimport StaticTuple,\
+    import_static_tuple_c, StaticTuple_New, \
+    StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact
+
+cdef extern from "_static_tuple_c.h":
+    # Defined explicitly rather than cimport-ing. Trying to use cimport, the
+    # type for PyObject is a different class that happens to have the same
+    # name...
+    PyObject * StaticTuple_GET_ITEM_ptr "StaticTuple_GET_ITEM" (StaticTuple,
+                                                                Py_ssize_t)
+
 cdef extern from "zlib.h":
     ctypedef unsigned long uLong
     ctypedef unsigned int uInt
@@ -60,8 +71,14 @@
     uLong crc32(uLong crc, Bytef *buf, uInt len)
 
 
+# Set up the StaticTuple C_API functionality
+import_static_tuple_c()
+
+cdef object _LeafNode
 _LeafNode = None
+cdef object _InternalNode
 _InternalNode = None
+cdef object _unknown
 _unknown = None
 
 # We shouldn't just copy this from _dirstate_helpers_pyx
@@ -91,9 +108,9 @@
     cdef char *c_out
     cdef PyObject *bit
 
-    if not PyTuple_CheckExact(key):
-        raise TypeError('key %r is not a tuple' % (key,))
-    num_bits = PyTuple_GET_SIZE(key)
+    if not StaticTuple_CheckExact(key):
+        raise TypeError('key %r is not a StaticTuple' % (key,))
+    num_bits = len(key)
     # 4 bytes per crc32, and another 1 byte between bits
     num_out_bytes = (9 * num_bits) - 1
     out = PyString_FromStringAndSize(NULL, num_out_bytes)
@@ -105,7 +122,7 @@
         # We use the _ptr variant, because GET_ITEM returns a borrowed
         # reference, and Pyrex assumes that returned 'object' are a new
         # reference
-        bit = PyTuple_GET_ITEM_ptr(key, i)
+        bit = StaticTuple_GET_ITEM_ptr(key, i)
         if not PyString_CheckExact_ptr(bit):
             raise TypeError('Bit %d of %r is not a string' % (i, key))
         c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
@@ -129,9 +146,9 @@
     cdef char *c_out
     cdef PyObject *bit
 
-    if not PyTuple_CheckExact(key):
-        raise TypeError('key %r is not a tuple' % (key,))
-    num_bits = PyTuple_GET_SIZE(key)
+    if not StaticTuple_CheckExact(key):
+        raise TypeError('key %r is not a StaticTuple' % (key,))
+    num_bits = len(key)
     # 4 bytes per crc32, and another 1 byte between bits
     num_out_bytes = (5 * num_bits) - 1
     out = PyString_FromStringAndSize(NULL, num_out_bytes)
@@ -140,10 +157,10 @@
         if i > 0:
             c_out[0] = c'\x00'
             c_out = c_out + 1
-        bit = PyTuple_GET_ITEM_ptr(key, i)
+        bit = StaticTuple_GET_ITEM_ptr(key, i)
         if not PyString_CheckExact_ptr(bit):
-            raise TypeError('Bit %d of %r is not a string: %r' % (i, key,
-            <object>bit))
+            raise TypeError('Bit %d of %r is not a string: %r'
+                            % (i, key, <object>bit))
         c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
         c_len = PyString_GET_SIZE_ptr(bit)
         crc_val = crc32(0, c_bit, c_len)
@@ -195,6 +212,7 @@
     cdef char *prefix, *value_start, *prefix_tail
     cdef char *next_null, *last_null, *line_start
     cdef char *c_entry, *entry_start
+    cdef StaticTuple entry_bits
 
     if _LeafNode is None:
         from bzrlib import chk_map
@@ -265,12 +283,14 @@
             if next_line == NULL:
                 raise ValueError('missing trailing newline')
             cur = next_line + 1
-        entry_bits = PyTuple_New(width)
+        entry_bits = StaticTuple_New(width)
         for i from 0 <= i < num_prefix_bits:
+            # TODO: Use PyList_GetItem, or turn prefix_bits into a
+            #       tuple/StaticTuple
             entry = prefix_bits[i]
             # SET_ITEM 'steals' a reference
             Py_INCREF(entry)
-            PyTuple_SET_ITEM(entry_bits, i, entry)
+            StaticTuple_SET_ITEM(entry_bits, i, entry)
         value = PyString_FromStringAndSize(value_start, next_line - value_start)
         # The next entry bit needs the 'tail' from the prefix, and first part
         # of the line
@@ -288,7 +308,7 @@
             memcpy(c_entry + prefix_tail_len, line_start, next_null - line_start)
         Py_INCREF(entry)
         i = num_prefix_bits
-        PyTuple_SET_ITEM(entry_bits, i, entry)
+        StaticTuple_SET_ITEM(entry_bits, i, entry)
         while next_null != last_null: # We have remaining bits
             i = i + 1
             if i > width:
@@ -301,11 +321,12 @@
             entry = PyString_FromStringAndSize(entry_start,
                                                next_null - entry_start)
             Py_INCREF(entry)
-            PyTuple_SET_ITEM(entry_bits, i, entry)
+            StaticTuple_SET_ITEM(entry_bits, i, entry)
         if len(entry_bits) != width:
             raise AssertionError(
                 'Incorrect number of elements (%d vs %d)'
                 % (len(entry_bits)+1, width + 1))
+        entry_bits = StaticTuple_Intern(entry_bits)
         PyDict_SetItem(items, entry_bits, value)
     if len(items) != length:
         raise ValueError("item count (%d) mismatch for key %s,"
@@ -343,6 +364,8 @@
         _unknown = chk_map._unknown
     result = _InternalNode(search_key_func=search_key_func)
 
+    if not StaticTuple_CheckExact(key):
+        raise TypeError('key %r is not a StaticTuple' % (key,))
     if not PyString_CheckExact(bytes):
         raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
 
@@ -384,7 +407,8 @@
         memcpy(c_item_prefix + prefix_length, cur, next_null - cur)
         flat_key = PyString_FromStringAndSize(next_null + 1,
                                               next_line - next_null - 1)
-        PyDict_SetItem(items, item_prefix, (flat_key,))
+        flat_key = StaticTuple(flat_key).intern()
+        PyDict_SetItem(items, item_prefix, flat_key)
         cur = next_line + 1
     assert len(items) > 0
     result._items = items
@@ -398,4 +422,3 @@
     result._node_width = len(item_prefix)
     result._search_prefix = PyString_FromStringAndSize(prefix, prefix_length)
     return result
-

=== modified file 'bzrlib/_dirstate_helpers_pyx.pyx'
--- bzrlib/_dirstate_helpers_pyx.pyx	2010-01-05 04:59:57 +0000
+++ bzrlib/_dirstate_helpers_pyx.pyx	2010-02-18 00:00:51 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2007, 2008 Canonical Ltd
+# Copyright (C) 2007-2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by

=== added file 'bzrlib/_export_c_api.h'
--- bzrlib/_export_c_api.h	1970-01-01 00:00:00 +0000
+++ bzrlib/_export_c_api.h	2010-02-18 00:00:51 +0000
@@ -0,0 +1,104 @@
+/* Copyright (C) 2009 Canonical Ltd
+ * 
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+
+/* This file contains helper functions for exporting a C API for a CPython
+ * extension module.
+ */
+
+#ifndef _EXPORT_C_API_H_
+#define _EXPORT_C_API_H_
+
+static const char *_C_API_NAME = "_C_API";
+
+/**
+ * Add a C function to the modules _C_API
+ * This wraps the function in a PyCObject, and inserts that into a dict.
+ * The key of the dict is the function name, and the description is the
+ * signature of the function.
+ * This is generally called during a modules init_MODULE function.
+ *
+ * @param   module  A Python module (the one being initialized)
+ * @param   funcname The name of the function being exported
+ * @param   func    A pointer to the function
+ * @param   signature The C signature of the function
+ * @return  0 if everything is successful, -1 if there is a problem. An
+ *          exception should also be set
+ */
+static int
+_export_function(PyObject *module, char *funcname, void *func, char *signature)
+{
+    PyObject *d = NULL;
+    PyObject *c_obj = NULL;
+
+    /* (char *) is because python2.4 declares this api as 'char *' rather than
+     * const char* which it really is.
+     */
+    d = PyObject_GetAttrString(module, (char *)_C_API_NAME);
+    if (!d) {
+        PyErr_Clear();
+        d = PyDict_New();
+        if (!d)
+            goto bad;
+        Py_INCREF(d);
+        if (PyModule_AddObject(module, (char *)_C_API_NAME, d) < 0)
+            goto bad;
+    }
+    c_obj = PyCObject_FromVoidPtrAndDesc(func, signature, 0);
+    if (!c_obj)
+        goto bad;
+    if (PyDict_SetItemString(d, funcname, c_obj) < 0)
+        goto bad;
+    Py_DECREF(d);
+    return 0;
+bad:
+    Py_XDECREF(c_obj);
+    Py_XDECREF(d);
+    return -1;
+}
+
+/* Note:
+ *  It feels like more could be done here. Specifically, if you look at
+ *  _static_tuple_c.h you can see some boilerplate where we have:
+ * #ifdef STATIC_TUPLE_MODULE  // are we exporting or importing
+ * static RETVAL FUNCNAME PROTO;
+ * #else
+ * static RETVAL (*FUNCNAME) PROTO;
+ * #endif
+ * 
+ * And then in _static_tuple_c.c we have
+ * int setup_c_api()
+ * {
+ *   _export_function(module, #FUNCNAME, FUNCNAME, #PROTO);
+ * }
+ *
+ * And then in _static_tuple_c.h import_##MODULE
+ * struct function_definition functions[] = {
+ *   {#FUNCNAME, (void **)&FUNCNAME, #RETVAL #PROTO},
+ *   ...
+ *   {NULL}};
+ *
+ * And some similar stuff for types. However, this would mean that we would
+ * need a way for the C preprocessor to build up a list of definitions to be
+ * generated, and then expand that list at the appropriate time.
+ * I would guess there would be a way to do this, but probably not without a
+ * lot of magic, and the end result probably wouldn't be very pretty to
+ * maintain. Perhaps python's dynamic nature has left me jaded about writing
+ * boilerplate....
+ */
+
+#endif // _EXPORT_C_API_H_

=== modified file 'bzrlib/_groupcompress_pyx.pyx'
--- bzrlib/_groupcompress_pyx.pyx	2010-01-05 04:59:57 +0000
+++ bzrlib/_groupcompress_pyx.pyx	2010-02-18 00:00:52 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2009 Canonical Ltd
+# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -31,10 +31,10 @@
 
 cdef extern from *:
     ctypedef unsigned long size_t
-    void * malloc(size_t)
-    void * realloc(void *, size_t)
-    void free(void *)
-    void memcpy(void *, void *, size_t)
+    void * malloc(size_t) nogil
+    void * realloc(void *, size_t) nogil
+    void free(void *) nogil
+    void memcpy(void *, void *, size_t) nogil
 
 
 cdef extern from "delta.h":
@@ -44,19 +44,16 @@
         unsigned long agg_offset
     struct delta_index:
         pass
-    delta_index * create_delta_index(source_info *src, delta_index *old)
+    delta_index * create_delta_index(source_info *src, delta_index *old) nogil
     delta_index * create_delta_index_from_delta(source_info *delta,
-                                                delta_index *old)
-    void free_delta_index(delta_index *index)
+                                                delta_index *old) nogil
+    void free_delta_index(delta_index *index) nogil
     void *create_delta(delta_index *indexes,
              void *buf, unsigned long bufsize,
-             unsigned long *delta_size, unsigned long max_delta_size)
+             unsigned long *delta_size, unsigned long max_delta_size) nogil
     unsigned long get_delta_hdr_size(unsigned char **datap,
-                                     unsigned char *top)
+                                     unsigned char *top) nogil
     Py_ssize_t DELTA_SIZE_MIN
-    void *patch_delta(void *src_buf, unsigned long src_size,
-                      void *delta_buf, unsigned long delta_size,
-                      unsigned long *dst_size)
 
 
 cdef void *safe_malloc(size_t count) except NULL:
@@ -148,7 +145,8 @@
         src.buf = c_delta
         src.size = c_delta_size
         src.agg_offset = self._source_offset + unadded_bytes
-        index = create_delta_index_from_delta(src, self._index)
+        with nogil:
+            index = create_delta_index_from_delta(src, self._index)
         self._source_offset = src.agg_offset + src.size
         if index != NULL:
             free_delta_index(self._index)
@@ -188,7 +186,8 @@
         self._source_offset = src.agg_offset + src.size
         # We delay creating the index on the first insert
         if source_location != 0:
-            index = create_delta_index(src, self._index)
+            with nogil:
+                index = create_delta_index(src, self._index)
             if index != NULL:
                 free_delta_index(self._index)
                 self._index = index
@@ -201,7 +200,8 @@
 
         # We know that self._index is already NULL, so whatever
         # create_delta_index returns is fine
-        self._index = create_delta_index(&self._source_infos[0], NULL)
+        with nogil:
+            self._index = create_delta_index(&self._source_infos[0], NULL)
         assert self._index != NULL
 
     cdef _expand_sources(self):
@@ -218,6 +218,7 @@
         cdef Py_ssize_t target_size
         cdef void * delta
         cdef unsigned long delta_size
+        cdef unsigned long c_max_delta_size
 
         if self._index == NULL:
             if len(self._sources) == 0:
@@ -234,9 +235,11 @@
         # TODO: inline some of create_delta so we at least don't have to double
         #       malloc, and can instead use PyString_FromStringAndSize, to
         #       allocate the bytes into the final string
-        delta = create_delta(self._index,
-                             target, target_size,
-                             &delta_size, max_delta_size)
+        c_max_delta_size = max_delta_size
+        with nogil:
+            delta = create_delta(self._index,
+                                 target, target_size,
+                                 &delta_size, c_max_delta_size)
         result = None
         if delta:
             result = PyString_FromStringAndSize(<char *>delta, delta_size)
@@ -276,7 +279,8 @@
 
 
 cdef unsigned char *_decode_copy_instruction(unsigned char *bytes,
-    unsigned char cmd, unsigned int *offset, unsigned int *length): # cannot_raise
+    unsigned char cmd, unsigned int *offset,
+    unsigned int *length) nogil: # cannot_raise
     """Decode a copy instruction from the next few bytes.
 
     A copy instruction is a variable number of bytes, so we will parse the
@@ -326,6 +330,7 @@
     cdef unsigned char *dst_buf, *out, cmd
     cdef Py_ssize_t size
     cdef unsigned int cp_off, cp_size
+    cdef int failed
 
     data = <unsigned char *>delta
     top = data + delta_size
@@ -335,37 +340,49 @@
     result = PyString_FromStringAndSize(NULL, size)
     dst_buf = <unsigned char*>PyString_AS_STRING(result)
 
-    out = dst_buf
-    while (data < top):
-        cmd = data[0]
-        data = data + 1
-        if (cmd & 0x80):
-            # Copy instruction
-            data = _decode_copy_instruction(data, cmd, &cp_off, &cp_size)
-            if (cp_off + cp_size < cp_size or
-                cp_off + cp_size > source_size or
-                cp_size > size):
-                raise RuntimeError('Something wrong with:'
-                    ' cp_off = %s, cp_size = %s'
-                    ' source_size = %s, size = %s'
-                    % (cp_off, cp_size, source_size, size))
-            memcpy(out, source + cp_off, cp_size)
-            out = out + cp_size
-            size = size - cp_size
-        else:
-            # Insert instruction
-            if cmd == 0:
-                # cmd == 0 is reserved for future encoding
-                # extensions. In the mean time we must fail when
-                # encountering them (might be data corruption).
-                raise RuntimeError('Got delta opcode: 0, not supported')
-            if (cmd > size):
-                raise RuntimeError('Insert instruction longer than remaining'
-                    ' bytes: %d > %d' % (cmd, size))
-            memcpy(out, data, cmd)
-            out = out + cmd
-            data = data + cmd
-            size = size - cmd
+    failed = 0
+    with nogil:
+        out = dst_buf
+        while (data < top):
+            cmd = data[0]
+            data = data + 1
+            if (cmd & 0x80):
+                # Copy instruction
+                data = _decode_copy_instruction(data, cmd, &cp_off, &cp_size)
+                if (cp_off + cp_size < cp_size or
+                    cp_off + cp_size > source_size or
+                    cp_size > size):
+                    failed = 1
+                    break
+                memcpy(out, source + cp_off, cp_size)
+                out = out + cp_size
+                size = size - cp_size
+            else:
+                # Insert instruction
+                if cmd == 0:
+                    # cmd == 0 is reserved for future encoding
+                    # extensions. In the mean time we must fail when
+                    # encountering them (might be data corruption).
+                    failed = 2
+                    break
+                if cmd > size:
+                    failed = 3
+                    break
+                memcpy(out, data, cmd)
+                out = out + cmd
+                data = data + cmd
+                size = size - cmd
+    if failed:
+        if failed == 1:
+            raise ValueError('Something wrong with:'
+                ' cp_off = %s, cp_size = %s'
+                ' source_size = %s, size = %s'
+                % (cp_off, cp_size, source_size, size))
+        elif failed == 2:
+            raise ValueError('Got delta opcode: 0, not supported')
+        elif failed == 3:
+            raise ValueError('Insert instruction longer than remaining'
+                ' bytes: %d > %d' % (cmd, size))
 
     # sanity check
     if (data != top or size != 0):

=== added file 'bzrlib/_import_c_api.h'
--- bzrlib/_import_c_api.h	1970-01-01 00:00:00 +0000
+++ bzrlib/_import_c_api.h	2010-02-18 00:00:51 +0000
@@ -0,0 +1,189 @@
+/* Copyright (C) 2009 Canonical Ltd
+ * 
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _IMPORT_C_API_H_
+#define _IMPORT_C_API_H_
+
+/**
+ * Helper functions to eliminate some of the boilerplate when importing a C API
+ * from a CPython extension module.
+ *
+ * For more information see _export_c_api.h
+ */
+
+static const char *_C_API_NAME = "_C_API";
+
+/**
+ * Import a function from the _C_API_NAME dict that is part of module.
+ *
+ * @param   module  The Python module we are importing from
+ *                  the attribute _C_API_NAME will be used as a dictionary
+ *                  containing the function pointer we are looking for.
+ * @param   funcname    Name of the function we want to import
+ * @param   func    A pointer to the function handle where we will store the
+ *                  function.
+ * @param   signature   The C signature of the function. This is validated
+ *                      against the signature stored in the C api, to make sure
+ *                      there is no versioning skew.
+ */
+static int _import_function(PyObject *module, const char *funcname,
+                            void **func, const char *signature)
+{
+    PyObject *d = NULL;
+    PyObject *c_obj = NULL;
+    const char *desc = NULL;
+
+    /* (char *) because Python2.4 defines this as (char *) rather than
+     * (const char *)
+     */
+    d = PyObject_GetAttrString(module, (char *)_C_API_NAME);
+    if (!d) {
+        // PyObject_GetAttrString sets an appropriate exception
+        goto bad;
+    }
+    c_obj = PyDict_GetItemString(d, funcname);
+    if (!c_obj) {
+        // PyDict_GetItemString does not set an exception
+        PyErr_Format(PyExc_AttributeError,
+            "Module %s did not export a function named %s\n",
+            PyModule_GetName(module), funcname);
+        goto bad;
+    }
+    desc = (char *)PyCObject_GetDesc(c_obj);
+    if (!desc || strcmp(desc, signature) != 0) {
+        if (desc == NULL) {
+            desc = "<null>";
+        }
+        PyErr_Format(PyExc_TypeError,
+            "C function %s.%s has wrong signature (expected %s, got %s)",
+                PyModule_GetName(module), funcname, signature, desc);
+        goto bad;
+    }
+    *func = PyCObject_AsVoidPtr(c_obj);
+    Py_DECREF(d);
+    return 0;
+bad:
+    Py_XDECREF(d);
+    return -1;
+}
+
+
+/**
+ * Get a pointer to an exported PyTypeObject.
+ *
+ * @param   module        The Python module we are importing from
+ * @param   class_name    Attribute of the module that should reference the
+ *                        Type object. Note that a PyTypeObject is the python
+ *                        description of the type, not the raw C structure.
+ * @return  A Pointer to the requested type object. On error NULL will be
+ *          returned and an exception will be set.
+ */
+static PyTypeObject *
+_import_type(PyObject *module, const char *class_name)
+{
+    PyObject *type = NULL;
+
+    type = PyObject_GetAttrString(module, (char *)class_name);
+    if (!type) {
+        goto bad;
+    }
+    if (!PyType_Check(type)) {
+        PyErr_Format(PyExc_TypeError,
+            "%s.%s is not a type object",
+            PyModule_GetName(module), class_name);
+        goto bad;
+    }
+    return (PyTypeObject *)type;
+bad:
+    Py_XDECREF(type);
+    return NULL;
+}
+
+
+struct function_description
+{
+    const char *name;
+    void **pointer;
+    const char *signature;
+};
+
+struct type_description
+{
+    const char *name;
+    PyTypeObject **pointer;
+};
+
+/**
+ * Helper for importing several functions and types in a data-driven manner.
+ *
+ * @param   module  The name of the module we will be importing
+ * @param   functions   A list of function_description objects, describing the
+ *                      functions being imported.
+ *                      The list should be terminated with {NULL} to indicate
+ *                      there are no more functions to import.
+ * @param   types       A list of type_description objects describing type
+ *                      objects that we want to import. The list should be
+ *                      terminated with {NULL} to indicate there are no more
+ *                      types to import.
+ * @return  0 on success, -1 on error and an exception should be set.
+ */
+
+static int
+_import_extension_module(const char *module_name,
+                         struct function_description *functions,
+                         struct type_description *types)
+{
+    PyObject *module = NULL;
+    struct function_description *cur_func;
+    struct type_description *cur_type;
+    int ret_code;
+    
+    module = PyImport_ImportModule((char *)module_name);
+    if (!module)
+        goto bad;
+    if (functions != NULL) {
+        cur_func = functions;
+        while (cur_func->name != NULL) {
+            ret_code = _import_function(module, cur_func->name,
+                                        cur_func->pointer,
+                                        cur_func->signature);
+            if (ret_code < 0)
+                goto bad;
+            cur_func++;
+        }
+    }
+    if (types != NULL) {
+        PyTypeObject *type_p = NULL;
+        cur_type = types;
+        while (cur_type->name != NULL)  {
+            type_p = _import_type(module, cur_type->name);
+            if (type_p == NULL)
+                goto bad;
+            *(cur_type->pointer) = type_p;
+            cur_type++;
+        }
+    }
+    
+    Py_XDECREF(module);
+    return 0;
+bad:
+    Py_XDECREF(module);
+    return -1;
+}
+
+
+#endif // _IMPORT_C_API_H_

=== modified file 'bzrlib/_knit_load_data_pyx.pyx'
--- bzrlib/_knit_load_data_pyx.pyx	2010-01-04 23:13:20 +0000
+++ bzrlib/_knit_load_data_pyx.pyx	2010-02-18 00:00:51 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2007 Canonical Ltd
+# Copyright (C) 2007-2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by

=== modified file 'bzrlib/_known_graph_py.py'
--- bzrlib/_known_graph_py.py	2009-08-25 18:45:40 +0000
+++ bzrlib/_known_graph_py.py	2010-02-18 00:00:52 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2009 Canonical Ltd
+# Copyright (C) 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -17,6 +17,7 @@
 """Implementation of Graph algorithms when we have already loaded everything.
 """
 
+from collections import deque
 from bzrlib import (
     errors,
     revision,
@@ -62,7 +63,7 @@
         :param parent_map: A dictionary mapping key => parent_keys
         """
         self._nodes = {}
-        # Maps {sorted(revision_id, revision_id): heads}
+        # Maps {frozenset(revision_id, revision_id): heads}
         self._known_heads = {}
         self.do_cache = do_cache
         self._initialize_nodes(parent_map)
@@ -132,6 +133,71 @@
                     # Update known_parent_gdfos for a key we couldn't process
                     known_parent_gdfos[child_key] = known_gdfo
 
+    def add_node(self, key, parent_keys):
+        """Add a new node to the graph.
+
+        If this fills in a ghost, then the gdfos of all children will be
+        updated accordingly.
+        
+        :param key: The node being added. If this is a duplicate, this is a
+            no-op.
+        :param parent_keys: The parents of the given node.
+        :return: None (should we return if this was a ghost, etc?)
+        """
+        nodes = self._nodes
+        if key in nodes:
+            node = nodes[key]
+            if node.parent_keys is None:
+                node.parent_keys = parent_keys
+                # A ghost is being added, we can no-longer trust the heads
+                # cache, so clear it
+                self._known_heads.clear()
+            else:
+                # Make sure we compare a list to a list, as tuple != list.
+                parent_keys = list(parent_keys)
+                existing_parent_keys = list(node.parent_keys)
+                if parent_keys == existing_parent_keys:
+                    return # Identical content
+                else:
+                    raise ValueError('Parent key mismatch, existing node %s'
+                        ' has parents of %s not %s'
+                        % (key, existing_parent_keys, parent_keys))
+        else:
+            node = _KnownGraphNode(key, parent_keys)
+            nodes[key] = node
+        parent_gdfo = 0
+        for parent_key in parent_keys:
+            try:
+                parent_node = nodes[parent_key]
+            except KeyError:
+                parent_node = _KnownGraphNode(parent_key, None)
+                # Ghosts and roots have gdfo 1
+                parent_node.gdfo = 1
+                nodes[parent_key] = parent_node
+            if parent_gdfo < parent_node.gdfo:
+                parent_gdfo = parent_node.gdfo
+            parent_node.child_keys.append(key)
+        node.gdfo = parent_gdfo + 1
+        # Now fill the gdfo to all children
+        # Note that this loop is slightly inefficient, in that we may visit the
+        # same child (and its decendents) more than once, however, it is
+        # 'efficient' in that we only walk to nodes that would be updated,
+        # rather than all nodes
+        # We use a deque rather than a simple list stack, to go for BFD rather
+        # than DFD. So that if a longer path is possible, we walk it before we
+        # get to the final child
+        pending = deque([node])
+        while pending:
+            node = pending.popleft()
+            next_gdfo = node.gdfo + 1
+            for child_key in node.child_keys:
+                child = nodes[child_key]
+                if child.gdfo < next_gdfo:
+                    # This child is being updated, we need to check its
+                    # children
+                    child.gdfo = next_gdfo
+                    pending.append(child)
+
     def heads(self, keys):
         """Return the heads from amongst keys.
 
@@ -281,3 +347,26 @@
                  in tsort.merge_sort(as_parent_map, tip_key,
                                      mainline_revisions=None,
                                      generate_revno=True)]
+    
+    def get_parent_keys(self, key):
+        """Get the parents for a key
+        
+        Returns a list containg the parents keys. If the key is a ghost,
+        None is returned. A KeyError will be raised if the key is not in
+        the graph.
+        
+        :param keys: Key to check (eg revision_id)
+        :return: A list of parents
+        """
+        return self._nodes[key].parent_keys
+
+    def get_child_keys(self, key):
+        """Get the children for a key
+        
+        Returns a list containg the children keys. A KeyError will be raised
+        if the key is not in the graph.
+        
+        :param keys: Key to check (eg revision_id)
+        :return: A list of children
+        """
+        return self._nodes[key].child_keys

=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- bzrlib/_known_graph_pyx.pyx	2010-01-05 05:03:51 +0000
+++ bzrlib/_known_graph_pyx.pyx	2010-02-18 00:00:51 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2009 Canonical Ltd
+# Copyright (C) 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -51,6 +51,7 @@
 
     void Py_INCREF(object)
 
+from collections import deque
 import gc
 
 from bzrlib import errors, revision
@@ -88,6 +89,18 @@
                 PyList_Append(keys, child.key)
             return keys
 
+    property parent_keys:
+        def __get__(self):
+            if self.parents is None:
+                return None
+            
+            cdef _KnownGraphNode parent
+
+            keys = []
+            for parent in self.parents:
+                PyList_Append(keys, parent.key)
+            return keys
+    
     cdef clear_references(self):
         self.parents = None
         self.children = None
@@ -180,7 +193,7 @@
     """This is a class which assumes we already know the full graph."""
 
     cdef public object _nodes
-    cdef object _known_heads
+    cdef public object _known_heads
     cdef public int do_cache
 
     def __init__(self, parent_map, do_cache=True):
@@ -220,6 +233,28 @@
             node = <_KnownGraphNode>temp_node
         return node
 
+    cdef _populate_parents(self, _KnownGraphNode node, parent_keys):
+        cdef Py_ssize_t num_parent_keys, pos
+        cdef _KnownGraphNode parent_node
+
+        num_parent_keys = len(parent_keys)
+        # We know how many parents, so we pre allocate the tuple
+        parent_nodes = PyTuple_New(num_parent_keys)
+        for pos from 0 <= pos < num_parent_keys:
+            # Note: it costs us 10ms out of 40ms to lookup all of these
+            #       parents, it doesn't seem to be an allocation overhead,
+            #       but rather a lookup overhead. There doesn't seem to be
+            #       a way around it, and that is one reason why
+            #       KnownGraphNode maintains a direct pointer to the parent
+            #       node.
+            # We use [] because parent_keys may be a tuple or list
+            parent_node = self._get_or_create_node(parent_keys[pos])
+            # PyTuple_SET_ITEM will steal a reference, so INCREF first
+            Py_INCREF(parent_node)
+            PyTuple_SET_ITEM(parent_nodes, pos, parent_node)
+            PyList_Append(parent_node.children, node)
+        node.parents = parent_nodes
+
     def _initialize_nodes(self, parent_map):
         """Populate self._nodes.
 
@@ -230,7 +265,7 @@
           child keys,
         """
         cdef PyObject *temp_key, *temp_parent_keys, *temp_node
-        cdef Py_ssize_t pos, pos2, num_parent_keys
+        cdef Py_ssize_t pos
         cdef _KnownGraphNode node
         cdef _KnownGraphNode parent_node
 
@@ -241,24 +276,8 @@
         while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
             key = <object>temp_key
             parent_keys = <object>temp_parent_keys
-            num_parent_keys = len(parent_keys)
             node = self._get_or_create_node(key)
-            # We know how many parents, so we pre allocate the tuple
-            parent_nodes = PyTuple_New(num_parent_keys)
-            for pos2 from 0 <= pos2 < num_parent_keys:
-                # Note: it costs us 10ms out of 40ms to lookup all of these
-                #       parents, it doesn't seem to be an allocation overhead,
-                #       but rather a lookup overhead. There doesn't seem to be
-                #       a way around it, and that is one reason why
-                #       KnownGraphNode maintains a direct pointer to the parent
-                #       node.
-                # We use [] because parent_keys may be a tuple or list
-                parent_node = self._get_or_create_node(parent_keys[pos2])
-                # PyTuple_SET_ITEM will steal a reference, so INCREF first
-                Py_INCREF(parent_node)
-                PyTuple_SET_ITEM(parent_nodes, pos2, parent_node)
-                PyList_Append(parent_node.children, node)
-            node.parents = parent_nodes
+            self._populate_parents(node, parent_keys)
 
     def _find_tails(self):
         cdef PyObject *temp_node
@@ -322,6 +341,76 @@
                     # anymore
                     child.seen = 0
 
+    def add_node(self, key, parent_keys):
+        """Add a new node to the graph.
+
+        If this fills in a ghost, then the gdfos of all children will be
+        updated accordingly.
+        
+        :param key: The node being added. If this is a duplicate, this is a
+            no-op.
+        :param parent_keys: The parents of the given node.
+        :return: None (should we return if this was a ghost, etc?)
+        """
+        cdef PyObject *maybe_node
+        cdef _KnownGraphNode node, parent_node, child_node
+        cdef long parent_gdfo, next_gdfo
+
+        maybe_node = PyDict_GetItem(self._nodes, key)
+        if maybe_node != NULL:
+            node = <_KnownGraphNode>maybe_node
+            if node.parents is None:
+                # We are filling in a ghost
+                self._populate_parents(node, parent_keys)
+                # We can't trust cached heads anymore
+                self._known_heads.clear()
+            else: # Ensure that the parent_key list matches
+                existing_parent_keys = []
+                for parent_node in node.parents:
+                    existing_parent_keys.append(parent_node.key)
+                # Make sure we use a list for the comparison, in case it was a
+                # tuple, etc
+                parent_keys = list(parent_keys)
+                if existing_parent_keys == parent_keys:
+                    # Exact match, nothing more to do
+                    return
+                else:
+                    raise ValueError('Parent key mismatch, existing node %s'
+                        ' has parents of %s not %s'
+                        % (key, existing_parent_keys, parent_keys))
+        else:
+            node = _KnownGraphNode(key)
+            PyDict_SetItem(self._nodes, key, node)
+            self._populate_parents(node, parent_keys)
+        parent_gdfo = 0
+        for parent_node in node.parents:
+            if parent_node.gdfo == -1:
+                # This is a newly introduced ghost, so it gets gdfo of 1
+                parent_node.gdfo = 1
+            if parent_gdfo < parent_node.gdfo:
+                parent_gdfo = parent_node.gdfo
+        node.gdfo = parent_gdfo + 1
+        # Now fill the gdfo to all children
+        # Note that this loop is slightly inefficient, in that we may visit the
+        # same child (and its decendents) more than once, however, it is
+        # 'efficient' in that we only walk to nodes that would be updated,
+        # rather than all nodes
+        # We use a deque rather than a simple list stack, to go for BFD rather
+        # than DFD. So that if a longer path is possible, we walk it before we
+        # get to the final child
+        pending = deque([node])
+        pending_popleft = pending.popleft
+        pending_append = pending.append
+        while pending:
+            node = pending_popleft()
+            next_gdfo = node.gdfo + 1
+            for child_node in node.children:
+                if child_node.gdfo < next_gdfo:
+                    # This child is being updated, we need to check its
+                    # children
+                    child_node.gdfo = next_gdfo
+                    pending_append(child_node)
+
     def heads(self, keys):
         """Return the heads from amongst keys.
 
@@ -549,6 +638,29 @@
         #       shown a specific impact, yet.
         sorter = _MergeSorter(self, tip_key)
         return sorter.topo_order()
+    
+    def get_parent_keys(self, key):
+        """Get the parents for a key
+        
+        Returns a list containg the parents keys. If the key is a ghost,
+        None is returned. A KeyError will be raised if the key is not in
+        the graph.
+        
+        :param keys: Key to check (eg revision_id)
+        :return: A list of parents
+        """
+        return self._nodes[key].parent_keys 
+
+    def get_child_keys(self, key):
+        """Get the children for a key
+        
+        Returns a list containg the children keys. A KeyError will be raised
+        if the key is not in the graph.
+        
+        :param keys: Key to check (eg revision_id)
+        :return: A list of children
+        """
+        return self._nodes[key].child_keys    
 
 
 cdef class _MergeSortNode:

=== modified file 'bzrlib/_patiencediff_c.c'
--- bzrlib/_patiencediff_c.c	2009-03-23 14:59:43 +0000
+++ bzrlib/_patiencediff_c.c	2010-02-18 00:00:51 +0000
@@ -298,7 +298,7 @@
         apos = SENTINEL;
         /* loop through all lines in the linked list */
         for (i = h[equiv].a_pos; i != SENTINEL; i = lines_a[i].next) {
-            /* the index is lower than alo, the the next line */
+            /* the index is lower than alo, continue to the next line */
             if (i < alo) {
                 h[equiv].a_pos = i;
                 continue;
@@ -319,7 +319,7 @@
         /* check for duplicates of this line in lines_b[blo:bhi] */
         /* loop through all lines in the linked list */
         for (i = h[equiv].b_pos; i != SENTINEL; i = lines_b[i].next) {
-            /* the index is lower than blo, the the next line */
+            /* the index is lower than blo, continue to the next line */
             if (i < blo) {
                 h[equiv].b_pos = i;
                 continue;

=== modified file 'bzrlib/_readdir_pyx.pyx'
--- bzrlib/_readdir_pyx.pyx	2009-12-23 02:19:04 +0000
+++ bzrlib/_readdir_pyx.pyx	2010-02-18 00:00:50 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2006, 2008, 2009 Canonical Ltd
+# Copyright (C) 2006, 2008, 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by

=== modified file 'bzrlib/_rio_pyx.pyx'
--- bzrlib/_rio_pyx.pyx	2010-01-05 04:59:57 +0000
+++ bzrlib/_rio_pyx.pyx	2010-02-18 00:00:52 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2009 Canonical Ltd
+# Copyright (C) 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by

=== added file 'bzrlib/_simple_set_pyx.pxd'
--- bzrlib/_simple_set_pyx.pxd	1970-01-01 00:00:00 +0000
+++ bzrlib/_simple_set_pyx.pxd	2010-02-18 00:00:50 +0000
@@ -0,0 +1,91 @@
+# Copyright (C) 2009, 2010 Canonical Ltd
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+"""Interface definition of a class like PySet but without caching the hash.
+
+This is generally useful when you want to 'intern' objects, etc. Note that this
+differs from Set in that we:
+  1) Don't have all of the .intersection, .difference, etc functions
+  2) Do return the object from the set via queries
+     eg. SimpleSet.add(key) => saved_key and SimpleSet[key] => saved_key
+"""
+
+cdef extern from "Python.h":
+    ctypedef struct PyObject:
+        pass
+
+
+cdef public api class SimpleSet [object SimpleSetObject, type SimpleSet_Type]:
+    """A class similar to PySet, but with simpler implementation.
+
+    The main advantage is that this class uses only 2N memory to store N
+    objects rather than 4N memory. The main trade-off is that we do not cache
+    the hash value of saved objects. As such, it is assumed that computing the
+    hash will be cheap (such as strings or tuples of strings, etc.)
+
+    This also differs in that you can get back the objects that are stored
+    (like a dict), but we also don't implement the complete list of 'set'
+    operations (difference, intersection, etc).
+    """
+    # Data structure definition:
+    #   This is a basic hash table using open addressing.
+    #       http://en.wikipedia.org/wiki/Open_addressing
+    #   Basically that means we keep an array of pointers to Python objects
+    #   (called a table). Each location in the array is called a 'slot'.
+    #
+    #   An empty slot holds a NULL pointer, a slot where there was an item
+    #   which was then deleted will hold a pointer to _dummy, and a filled slot
+    #   points at the actual object which fills that slot.
+    #
+    #   The table is always a power of two, and the default location where an
+    #   object is inserted is at hash(object) & (table_size - 1)
+    #
+    #   If there is a collision, then we search for another location. The
+    #   specific algorithm is in _lookup. We search until we:
+    #       find the object
+    #       find an equivalent object (by tp_richcompare(obj1, obj2, Py_EQ))
+    #       find a NULL slot
+    #
+    #   When an object is deleted, we set its slot to _dummy. this way we don't
+    #   have to track whether there was a collision, and find the corresponding
+    #   keys. (The collision resolution algorithm makes that nearly impossible
+    #   anyway, because it depends on the upper bits of the hash.)
+    #   The main effect of this, is that if we find _dummy, then we can insert
+    #   an object there, but we have to keep searching until we find NULL to
+    #   know that the object is not present elsewhere.
+
+    cdef Py_ssize_t _used   # active
+    cdef Py_ssize_t _fill   # active + dummy
+    cdef Py_ssize_t _mask   # Table contains (mask+1) slots, a power of 2
+    cdef PyObject **_table  # Pyrex/Cython doesn't support arrays to 'object'
+                            # so we manage it manually
+
+    cdef PyObject *_get(self, object key) except? NULL
+    cdef object _add(self, key)
+    cdef int _discard(self, key) except -1
+    cdef int _insert_clean(self, PyObject *key) except -1
+    cdef Py_ssize_t _resize(self, Py_ssize_t min_unused) except -1
+
+
+# TODO: might want to export the C api here, though it is all available from
+#       the class object...
+cdef api SimpleSet SimpleSet_New()
+cdef api object SimpleSet_Add(object self, object key)
+cdef api int SimpleSet_Contains(object self, object key) except -1
+cdef api int SimpleSet_Discard(object self, object key) except -1
+cdef api PyObject *SimpleSet_Get(SimpleSet self, object key) except? NULL
+cdef api Py_ssize_t SimpleSet_Size(object self) except -1
+cdef api int SimpleSet_Next(object self, Py_ssize_t *pos, PyObject **key) except -1

=== added file 'bzrlib/_simple_set_pyx.pyx'
--- bzrlib/_simple_set_pyx.pyx	1970-01-01 00:00:00 +0000
+++ bzrlib/_simple_set_pyx.pyx	2010-02-18 00:00:50 +0000
@@ -0,0 +1,592 @@
+# Copyright (C) 2009, 2010 Canonical Ltd
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+"""Definition of a class that is similar to Set with some small changes."""
+
+cdef extern from "python-compat.h":
+    pass
+
+cdef extern from "Python.h":
+    ctypedef unsigned long size_t
+    ctypedef long (*hashfunc)(PyObject*) except -1
+    ctypedef object (*richcmpfunc)(PyObject *, PyObject *, int)
+    ctypedef int (*visitproc)(PyObject *, void *)
+    ctypedef int (*traverseproc)(PyObject *, visitproc, void *)
+    int Py_EQ
+    void Py_INCREF(PyObject *)
+    void Py_DECREF(PyObject *)
+    ctypedef struct PyTypeObject:
+        hashfunc tp_hash
+        richcmpfunc tp_richcompare
+        traverseproc tp_traverse
+
+    PyTypeObject *Py_TYPE(PyObject *)
+    # Note: *Don't* use hash(), Pyrex 0.9.8.5 thinks it returns an 'int', and
+    #       thus silently truncates to 32-bits on 64-bit machines.
+    long PyObject_Hash(PyObject *) except -1
+        
+    void *PyMem_Malloc(size_t nbytes)
+    void PyMem_Free(void *)
+    void memset(void *, int, size_t)
+
+
+# Dummy is an object used to mark nodes that have been deleted. Since
+# collisions require us to move a node to an alternative location, if we just
+# set an entry to NULL on delete, we won't find any relocated nodes.
+# We have to use _dummy_obj because we need to keep a refcount to it, but we
+# also use _dummy as a pointer, because it avoids having to put <PyObject*> all
+# over the code base.
+cdef object _dummy_obj
+cdef PyObject *_dummy
+_dummy_obj = object()
+_dummy = <PyObject *>_dummy_obj
+
+
+cdef object _NotImplemented
+_NotImplemented = NotImplemented
+
+
+cdef int _is_equal(PyObject *this, long this_hash, PyObject *other) except -1:
+    cdef long other_hash
+
+    if this == other:
+        return 1
+    other_hash = PyObject_Hash(other)
+    if other_hash != this_hash:
+        return 0
+
+    # This implements a subset of the PyObject_RichCompareBool functionality.
+    # Namely it:
+    #   1) Doesn't try to do anything with old-style classes
+    #   2) Assumes that both objects have a tp_richcompare implementation, and
+    #      that if that is not enough to compare equal, then they are not
+    #      equal. (It doesn't try to cast them both to some intermediate form
+    #      that would compare equal.)
+    res = Py_TYPE(this).tp_richcompare(this, other, Py_EQ)
+    if res is _NotImplemented:
+        res = Py_TYPE(other).tp_richcompare(other, this, Py_EQ)
+        if res is _NotImplemented:
+            return 0
+    if res:
+        return 1
+    return 0
+
+
+cdef public api class SimpleSet [object SimpleSetObject, type SimpleSet_Type]:
+    """This class can be used to track canonical forms for objects.
+
+    It is similar in function to the interned dictionary that is used by
+    strings. However:
+
+      1) It assumes that hash(obj) is cheap, so does not need to inline a copy
+         of it
+      2) It only stores one reference to the object, rather than 2 (key vs
+         key:value)
+
+    As such, it uses 1/3rd the amount of memory to store a pointer to the
+    interned object.
+    """
+    # Attributes are defined in the .pxd file
+    DEF DEFAULT_SIZE=1024
+
+    def __init__(self):
+        cdef Py_ssize_t size, n_bytes
+
+        size = DEFAULT_SIZE
+        self._mask = size - 1
+        self._used = 0
+        self._fill = 0
+        n_bytes = sizeof(PyObject*) * size;
+        self._table = <PyObject **>PyMem_Malloc(n_bytes)
+        if self._table == NULL:
+            raise MemoryError()
+        memset(self._table, 0, n_bytes)
+
+    def __dealloc__(self):
+        if self._table != NULL:
+            PyMem_Free(self._table)
+            self._table = NULL
+
+    property used:
+        def __get__(self):
+            return self._used
+
+    property fill:
+        def __get__(self):
+            return self._fill
+
+    property mask:
+        def __get__(self):
+            return self._mask
+
+    def _memory_size(self):
+        """Return the number of bytes of memory consumed by this class."""
+        return sizeof(self) + (sizeof(PyObject*)*(self._mask + 1))
+
+    def __len__(self):
+        return self._used
+
+    def _test_lookup(self, key):
+        cdef PyObject **slot
+
+        slot = _lookup(self, key)
+        if slot[0] == NULL:
+            res = '<null>'
+        elif slot[0] == _dummy:
+            res = '<dummy>'
+        else:
+            res = <object>slot[0]
+        return <int>(slot - self._table), res
+
+    def __contains__(self, key):
+        """Is key present in this SimpleSet."""
+        cdef PyObject **slot
+
+        slot = _lookup(self, key)
+        if slot[0] == NULL or slot[0] == _dummy:
+            return False
+        return True
+
+    cdef PyObject *_get(self, object key) except? NULL:
+        """Return the object (or nothing) define at the given location."""
+        cdef PyObject **slot
+
+        slot = _lookup(self, key)
+        if slot[0] == NULL or slot[0] == _dummy:
+            return NULL
+        return slot[0]
+
+    def __getitem__(self, key):
+        """Return a stored item that is equivalent to key."""
+        cdef PyObject *py_val
+
+        py_val = self._get(key)
+        if py_val == NULL:
+            raise KeyError("Key %s is not present" % key)
+        val = <object>(py_val)
+        return val
+
+    cdef int _insert_clean(self, PyObject *key) except -1:
+        """Insert a key into self.table.
+
+        This is only meant to be used during times like '_resize',
+        as it makes a lot of assuptions about keys not already being present,
+        and there being no dummy entries.
+        """
+        cdef size_t i, n_lookup
+        cdef long the_hash
+        cdef PyObject **table, **slot
+        cdef Py_ssize_t mask
+
+        mask = self._mask
+        table = self._table
+
+        the_hash = PyObject_Hash(key)
+        i = the_hash
+        for n_lookup from 0 <= n_lookup <= <size_t>mask: # Don't loop forever
+            slot = &table[i & mask]
+            if slot[0] == NULL:
+                slot[0] = key
+                self._fill = self._fill + 1
+                self._used = self._used + 1
+                return 1
+            i = i + 1 + n_lookup
+        raise RuntimeError('ran out of slots.')
+
+    def _py_resize(self, min_used):
+        """Do not use this directly, it is only exposed for testing."""
+        return self._resize(min_used)
+
+    cdef Py_ssize_t _resize(self, Py_ssize_t min_used) except -1:
+        """Resize the internal table.
+
+        The final table will be big enough to hold at least min_used entries.
+        We will copy the data from the existing table over, leaving out dummy
+        entries.
+
+        :return: The new size of the internal table
+        """
+        cdef Py_ssize_t new_size, n_bytes, remaining
+        cdef PyObject **new_table, **old_table, **slot
+
+        new_size = DEFAULT_SIZE
+        while new_size <= min_used and new_size > 0:
+            new_size = new_size << 1
+        # We rolled over our signed size field
+        if new_size <= 0:
+            raise MemoryError()
+        # Even if min_used == self._mask + 1, and we aren't changing the actual
+        # size, we will still run the algorithm so that dummy entries are
+        # removed
+        # TODO: Test this
+        # if new_size < self._used:
+        #     raise RuntimeError('cannot shrink SimpleSet to something'
+        #                        ' smaller than the number of used slots.')
+        n_bytes = sizeof(PyObject*) * new_size;
+        new_table = <PyObject **>PyMem_Malloc(n_bytes)
+        if new_table == NULL:
+            raise MemoryError()
+
+        old_table = self._table
+        self._table = new_table
+        memset(self._table, 0, n_bytes)
+        self._mask = new_size - 1
+        self._used = 0
+        remaining = self._fill
+        self._fill = 0
+
+        # Moving everything to the other table is refcount neutral, so we don't
+        # worry about it.
+        slot = old_table
+        while remaining > 0:
+            if slot[0] == NULL: # unused slot
+                pass 
+            elif slot[0] == _dummy: # dummy slot
+                remaining = remaining - 1
+            else: # active slot
+                remaining = remaining - 1
+                self._insert_clean(slot[0])
+            slot = slot + 1
+        PyMem_Free(old_table)
+        return new_size
+
+    def add(self, key):
+        """Similar to set.add(), start tracking this key.
+        
+        There is one small difference, which is that we return the object that
+        is stored at the given location. (which is closer to the
+        dict.setdefault() functionality.)
+        """
+        return self._add(key)
+
+    cdef object _add(self, key):
+        cdef PyObject **slot, *py_key
+        cdef int added
+
+        py_key = <PyObject *>key
+        if (Py_TYPE(py_key).tp_richcompare == NULL
+            or Py_TYPE(py_key).tp_hash == NULL):
+            raise TypeError('Types added to SimpleSet must implement'
+                            ' both tp_richcompare and tp_hash')
+        added = 0
+        # We need at least one empty slot
+        assert self._used < self._mask
+        slot = _lookup(self, key)
+        if (slot[0] == NULL):
+            Py_INCREF(py_key)
+            self._fill = self._fill + 1
+            self._used = self._used + 1
+            slot[0] = py_key
+            added = 1
+        elif (slot[0] == _dummy):
+            Py_INCREF(py_key)
+            self._used = self._used + 1
+            slot[0] = py_key
+            added = 1
+        # No else: clause. If _lookup returns a pointer to
+        # a live object, then we already have a value at this location.
+        retval = <object>(slot[0])
+        # PySet and PyDict use a 2-3rds full algorithm, we'll follow suit
+        if added and (self._fill * 3) >= ((self._mask + 1) * 2):
+            # However, we always work for a load factor of 2:1
+            self._resize(self._used * 2)
+        # Even if we resized and ended up moving retval into a different slot,
+        # it is still the value that is held at the slot equivalent to 'key',
+        # so we can still return it
+        return retval
+
+    def discard(self, key):
+        """Remove key from the set, whether it exists or not.
+
+        :return: False if the item did not exist, True if it did
+        """
+        if self._discard(key):
+            return True
+        return False
+
+    cdef int _discard(self, key) except -1:
+        cdef PyObject **slot, *py_key
+
+        slot = _lookup(self, key)
+        if slot[0] == NULL or slot[0] == _dummy:
+            return 0
+        self._used = self._used - 1
+        Py_DECREF(slot[0])
+        slot[0] = _dummy
+        # PySet uses the heuristic: If more than 1/5 are dummies, then resize
+        #                           them away
+        #   if ((so->_fill - so->_used) * 5 < so->mask)
+        # However, we are planning on using this as an interning structure, in
+        # which we will be putting a lot of objects. And we expect that large
+        # groups of them are going to have the same lifetime.
+        # Dummy entries hurt a little bit because they cause the lookup to keep
+        # searching, but resizing is also rather expensive
+        # For now, we'll just use their algorithm, but we may want to revisit
+        # it
+        if ((self._fill - self._used) * 5 > self._mask):
+            self._resize(self._used * 2)
+        return 1
+
+    def __iter__(self):
+        return _SimpleSet_iterator(self)
+
+
+cdef class _SimpleSet_iterator:
+    """Iterator over the SimpleSet structure."""
+
+    cdef Py_ssize_t pos
+    cdef SimpleSet set
+    cdef Py_ssize_t _used # track if things have been mutated while iterating
+    cdef Py_ssize_t len # number of entries left
+
+    def __init__(self, obj):
+        self.set = obj
+        self.pos = 0
+        self._used = self.set._used
+        self.len = self.set._used
+
+    def __iter__(self):
+        return self
+
+    def __next__(self):
+        cdef Py_ssize_t mask, i
+        cdef PyObject *key
+
+        if self.set is None:
+            raise StopIteration
+        if self.set._used != self._used:
+            # Force this exception to continue to be raised
+            self._used = -1
+            raise RuntimeError("Set size changed during iteration")
+        if not SimpleSet_Next(self.set, &self.pos, &key):
+            self.set = None
+            raise StopIteration
+        # we found something
+        the_key = <object>key # INCREF
+        self.len = self.len - 1
+        return the_key
+
+    def __length_hint__(self):
+        if self.set is not None and self._used == self.set._used:
+            return self.len
+        return 0
+    
+
+
+cdef api SimpleSet SimpleSet_New():
+    """Create a new SimpleSet object."""
+    return SimpleSet()
+
+
+cdef SimpleSet _check_self(object self):
+    """Check that the parameter is not None.
+
+    Pyrex/Cython will do type checking, but only to ensure that an object is
+    either the right type or None. You can say "object foo not None" for pure
+    python functions, but not for C functions.
+    So this is just a helper for all the apis that need to do the check.
+    """
+    cdef SimpleSet true_self
+    if self is None:
+        raise TypeError('self must not be None')
+    true_self = self
+    return true_self
+
+
+cdef PyObject **_lookup(SimpleSet self, object key) except NULL:
+    """Find the slot where 'key' would fit.
+
+    This is the same as a dicts 'lookup' function.
+
+    :param key: An object we are looking up
+    :param hash: The hash for key
+    :return: The location in self.table where key should be put.
+        location == NULL is an exception, but (*location) == NULL just
+        indicates the slot is empty and can be used.
+    """
+    # This uses Quadratic Probing:
+    #  http://en.wikipedia.org/wiki/Quadratic_probing
+    # with c1 = c2 = 1/2
+    # This leads to probe locations at:
+    #  h0 = hash(k1)
+    #  h1 = h0 + 1
+    #  h2 = h0 + 3 = h1 + 1 + 1
+    #  h3 = h0 + 6 = h2 + 1 + 2
+    #  h4 = h0 + 10 = h2 + 1 + 3
+    # Note that all of these are '& mask', but that is computed *after* the
+    # offset.
+    # This differs from the algorithm used by Set and Dict. Which, effectively,
+    # use double-hashing, and a step size that starts large, but dwindles to
+    # stepping one-by-one.
+    # This gives more 'locality' in that if you have a collision at offset X,
+    # the first fallback is X+1, which is fast to check. However, that means
+    # that an object w/ hash X+1 will also check there, and then X+2 next.
+    # However, for objects with differing hashes, their chains are different.
+    # The former checks X, X+1, X+3, ... the latter checks X+1, X+2, X+4, ...
+    # So different hashes diverge quickly.
+    # A bigger problem is that we *only* ever use the lowest bits of the hash
+    # So all integers (x + SIZE*N) will resolve into the same bucket, and all
+    # use the same collision resolution. We may want to try to find a way to
+    # incorporate the upper bits of the hash with quadratic probing. (For
+    # example, X, X+1, X+3+some_upper_bits, X+6+more_upper_bits, etc.)
+    cdef size_t i, n_lookup
+    cdef Py_ssize_t mask
+    cdef long key_hash
+    cdef PyObject **table, **slot, *cur, **free_slot, *py_key
+
+    py_key = <PyObject *>key
+    # Note: avoid using hash(obj) because of a bug w/ pyrex 0.9.8.5 and 64-bit
+    #       (it treats hash() as returning an 'int' rather than a 'long')
+    key_hash = PyObject_Hash(py_key)
+    i = <size_t>key_hash
+    mask = self._mask
+    table = self._table
+    free_slot = NULL
+    for n_lookup from 0 <= n_lookup <= <size_t>mask: # Don't loop forever
+        slot = &table[i & mask]
+        cur = slot[0]
+        if cur == NULL:
+            # Found a blank spot
+            if free_slot != NULL:
+                # Did we find an earlier _dummy entry?
+                return free_slot
+            else:
+                return slot
+        if cur == py_key:
+            # Found an exact pointer to the key
+            return slot
+        if cur == _dummy:
+            if free_slot == NULL:
+                free_slot = slot
+        elif _is_equal(py_key, key_hash, cur):
+            # Both py_key and cur belong in this slot, return it
+            return slot
+        i = i + 1 + n_lookup
+    raise AssertionError('should never get here')
+
+
+cdef api PyObject **_SimpleSet_Lookup(object self, object key) except NULL:
+    """Find the slot where 'key' would fit.
+
+    This is the same as a dicts 'lookup' function. This is a private
+    api because mutating what you get without maintaing the other invariants
+    is a 'bad thing'.
+
+    :param key: An object we are looking up
+    :param hash: The hash for key
+    :return: The location in self._table where key should be put
+        should never be NULL, but may reference a NULL (PyObject*)
+    """
+    return _lookup(_check_self(self), key)
+
+
+cdef api object SimpleSet_Add(object self, object key):
+    """Add a key to the SimpleSet (set).
+
+    :param self: The SimpleSet to add the key to.
+    :param key: The key to be added. If the key is already present,
+        self will not be modified
+    :return: The current key stored at the location defined by 'key'.
+        This may be the same object, or it may be an equivalent object.
+        (consider dict.setdefault(key, key))
+    """
+    return _check_self(self)._add(key)
+    
+
+cdef api int SimpleSet_Contains(object self, object key) except -1:
+    """Is key present in self?"""
+    return (key in _check_self(self))
+
+
+cdef api int SimpleSet_Discard(object self, object key) except -1:
+    """Remove the object referenced at location 'key'.
+
+    :param self: The SimpleSet being modified
+    :param key: The key we are checking on
+    :return: 1 if there was an object present, 0 if there was not, and -1 on
+        error.
+    """
+    return _check_self(self)._discard(key)
+
+
+cdef api PyObject *SimpleSet_Get(SimpleSet self, object key) except? NULL:
+    """Get a pointer to the object present at location 'key'.
+
+    This returns an object which is equal to key which was previously added to
+    self. This returns a borrowed reference, as it may also return NULL if no
+    value is present at that location.
+
+    :param key: The value we are looking for
+    :return: The object present at that location
+    """
+    return _check_self(self)._get(key)
+
+
+cdef api Py_ssize_t SimpleSet_Size(object self) except -1:
+    """Get the number of active entries in 'self'"""
+    return _check_self(self)._used
+
+
+cdef api int SimpleSet_Next(object self, Py_ssize_t *pos,
+                            PyObject **key) except -1:
+    """Walk over items in a SimpleSet.
+
+    :param pos: should be initialized to 0 by the caller, and will be updated
+        by this function
+    :param key: Will return a borrowed reference to key
+    :return: 0 if nothing left, 1 if we are returning a new value
+    """
+    cdef Py_ssize_t i, mask
+    cdef SimpleSet true_self
+    cdef PyObject **table
+    true_self = _check_self(self)
+    i = pos[0]
+    if (i < 0):
+        return 0
+    mask = true_self._mask
+    table= true_self._table
+    while (i <= mask and (table[i] == NULL or table[i] == _dummy)):
+        i = i + 1
+    pos[0] = i + 1
+    if (i > mask):
+        return 0 # All done
+    if (key != NULL):
+        key[0] = table[i]
+    return 1
+
+
+cdef int SimpleSet_traverse(SimpleSet self, visitproc visit,
+                            void *arg) except -1:
+    """This is an implementation of 'tp_traverse' that hits the whole table.
+
+    Cython/Pyrex don't seem to let you define a tp_traverse, and they only
+    define one for you if you have an 'object' attribute. Since they don't
+    support C arrays of objects, we access the PyObject * directly.
+    """
+    cdef Py_ssize_t pos
+    cdef PyObject *next_key
+    cdef int ret
+
+    pos = 0
+    while SimpleSet_Next(self, &pos, &next_key):
+        ret = visit(next_key, arg)
+        if ret:
+            return ret
+    return 0
+
+# It is a little bit ugly to do this, but it works, and means that Meliae can
+# dump the total memory consumed by all child objects.
+(<PyTypeObject *>SimpleSet).tp_traverse = <traverseproc>SimpleSet_traverse

=== added file 'bzrlib/_static_tuple_c.c'
--- bzrlib/_static_tuple_c.c	1970-01-01 00:00:00 +0000
+++ bzrlib/_static_tuple_c.c	2010-02-18 00:00:52 +0000
@@ -0,0 +1,945 @@
+/* Copyright (C) 2009, 2010 Canonical Ltd
+ * 
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/* Must be defined before importing _static_tuple_c.h so that we get the right
+ * linkage.
+ */
+#define STATIC_TUPLE_MODULE
+
+#include <Python.h>
+#include "python-compat.h"
+
+#include "_static_tuple_c.h"
+#include "_export_c_api.h"
+
+/* Pyrex 0.9.6.4 exports _simple_set_pyx_api as
+ * import__simple_set_pyx(), while Pyrex 0.9.8.5 and Cython 0.11.3 export them
+ * as import_bzrlib___simple_set_pyx(). As such, we just #define one to be
+ * equivalent to the other in our internal code.
+ */
+#define import__simple_set_pyx import_bzrlib___simple_set_pyx
+#include "_simple_set_pyx_api.h"
+
+#if defined(__GNUC__)
+#   define inline __inline__
+#elif defined(_MSC_VER)
+#   define inline __inline
+#else
+#   define inline
+#endif
+
+
+/* The one and only StaticTuple with no values */
+static StaticTuple *_empty_tuple = NULL;
+static PyObject *_interned_tuples = NULL;
+
+
+static inline int
+_StaticTuple_is_interned(StaticTuple *self)
+{
+    return self->flags & STATIC_TUPLE_INTERNED_FLAG;
+}
+
+
+
+static PyObject *
+StaticTuple_as_tuple(StaticTuple *self)
+{
+    PyObject *tpl = NULL, *obj = NULL;
+    int i, len;
+
+    len = self->size;
+    tpl = PyTuple_New(len);
+    if (!tpl) {
+        /* Malloc failure */
+        return NULL;
+    }
+    for (i = 0; i < len; ++i) {
+        obj = (PyObject *)self->items[i];
+        Py_INCREF(obj);
+        PyTuple_SET_ITEM(tpl, i, obj);
+    }
+    return tpl;
+}
+
+
+static char StaticTuple_as_tuple_doc[] = "as_tuple() => tuple";
+
+static StaticTuple *
+StaticTuple_Intern(StaticTuple *self)
+{
+    PyObject *canonical_tuple = NULL;
+
+    if (_interned_tuples == NULL || _StaticTuple_is_interned(self)) {
+        Py_INCREF(self);
+        return self;
+    }
+    /* SimpleSet_Add returns whatever object is present at self
+     * or the new object if it needs to add it.
+     */
+    canonical_tuple = SimpleSet_Add(_interned_tuples, (PyObject *)self);
+    if (!canonical_tuple) {
+        // Some sort of exception, propogate it.
+        return NULL;
+    }
+    if (canonical_tuple != (PyObject *)self) {
+        // There was already a tuple with that value
+        return (StaticTuple *)canonical_tuple;
+    }
+    self->flags |= STATIC_TUPLE_INTERNED_FLAG;
+    // The two references in the dict do not count, so that the StaticTuple
+    // object does not become immortal just because it was interned.
+    Py_REFCNT(self) -= 1;
+    return self;
+}
+
+static char StaticTuple_Intern_doc[] = "intern() => unique StaticTuple\n"
+    "Return a 'canonical' StaticTuple object.\n"
+    "Similar to intern() for strings, this makes sure there\n"
+    "is only one StaticTuple object for a given value\n."
+    "Common usage is:\n"
+    "  key = StaticTuple('foo', 'bar').intern()\n";
+
+
+static void
+StaticTuple_dealloc(StaticTuple *self)
+{
+    int i, len;
+
+    if (_StaticTuple_is_interned(self)) {
+        /* revive dead object temporarily for Discard */
+        Py_REFCNT(self) = 2;
+        if (SimpleSet_Discard(_interned_tuples, (PyObject*)self) != 1)
+            Py_FatalError("deletion of interned StaticTuple failed");
+        self->flags &= ~STATIC_TUPLE_INTERNED_FLAG;
+    }
+    len = self->size;
+    for (i = 0; i < len; ++i) {
+        Py_XDECREF(self->items[i]);
+    }
+    Py_TYPE(self)->tp_free((PyObject *)self);
+}
+
+
+/* Similar to PyTuple_New() */
+static StaticTuple *
+StaticTuple_New(Py_ssize_t size)
+{
+    StaticTuple *stuple;
+
+    if (size < 0 || size > 255) {
+        /* Too big or too small */
+        PyErr_SetString(PyExc_ValueError, "StaticTuple(...)"
+            " takes from 0 to 255 items");
+        return NULL;
+    }
+    if (size == 0 && _empty_tuple != NULL) {
+        Py_INCREF(_empty_tuple);
+        return _empty_tuple;
+    }
+    /* Note that we use PyObject_NewVar because we want to allocate a variable
+     * width entry. However we *aren't* truly a PyVarObject because we don't
+     * use a long for ob_size. Instead we use a plain 'size' that is an int,
+     * and will be overloaded with flags in the future.
+     * As such we do the alloc, and then have to clean up anything it does
+     * incorrectly.
+     */
+    stuple = PyObject_NewVar(StaticTuple, &StaticTuple_Type, size);
+    if (stuple == NULL) {
+        return NULL;
+    }
+    stuple->size = size;
+    stuple->flags = 0;
+    stuple->_unused0 = 0;
+    stuple->_unused1 = 0;
+    if (size > 0) {
+        memset(stuple->items, 0, sizeof(PyObject *) * size);
+    }
+#if STATIC_TUPLE_HAS_HASH
+    stuple->hash = -1;
+#endif
+    return stuple;
+}
+
+
+static StaticTuple *
+StaticTuple_FromSequence(PyObject *sequence)
+{
+    StaticTuple *new = NULL;
+    PyObject *as_tuple = NULL;
+    PyObject *item;
+    Py_ssize_t i, size;
+
+    if (StaticTuple_CheckExact(sequence)) {
+        Py_INCREF(sequence);
+        return (StaticTuple *)sequence;
+    }
+    if (!PySequence_Check(sequence)) {
+        as_tuple = PySequence_Tuple(sequence);
+        if (as_tuple == NULL)
+            goto done;
+        sequence = as_tuple;
+    }
+    size = PySequence_Size(sequence);
+    if (size == -1) {
+        goto done;
+    }
+    new = StaticTuple_New(size);
+    if (new == NULL) {
+        goto done;
+    }
+    for (i = 0; i < size; ++i) {
+        // This returns a new reference, which we then 'steal' with 
+        // StaticTuple_SET_ITEM
+        item = PySequence_GetItem(sequence, i);
+        if (item == NULL) {
+            Py_DECREF(new);
+            new = NULL;
+            goto done;
+        }
+        StaticTuple_SET_ITEM(new, i, item);
+    }
+done:
+    Py_XDECREF(as_tuple);
+    return (StaticTuple *)new;
+}
+
+static StaticTuple *
+StaticTuple_from_sequence(PyObject *self, PyObject *args, PyObject *kwargs)
+{
+    PyObject *sequence;
+    if (!PyArg_ParseTuple(args, "O", &sequence))
+        return NULL;
+    return StaticTuple_FromSequence(sequence);
+}
+
+
+/* Check that all items we point to are 'valid' */
+static int
+StaticTuple_check_items(StaticTuple *self)
+{
+    int i;
+    PyObject *obj;
+
+    for (i = 0; i < self->size; ++i) {
+        obj = self->items[i];
+        if (obj == NULL) {
+            PyErr_SetString(PyExc_RuntimeError, "StaticTuple(...)"
+                " should not have a NULL entry.");
+            return 0;
+        }
+        if (PyString_CheckExact(obj)
+            || StaticTuple_CheckExact(obj)
+            || obj == Py_None
+            || PyBool_Check(obj)
+            || PyInt_CheckExact(obj)
+            || PyLong_CheckExact(obj)
+            || PyFloat_CheckExact(obj)
+            || PyUnicode_CheckExact(obj)
+            ) continue;
+        PyErr_Format(PyExc_TypeError, "StaticTuple(...)"
+            " requires that all items are one of"
+            " str, StaticTuple, None, bool, int, long, float, or unicode"
+            " not %s.", Py_TYPE(obj)->tp_name);
+        return 0;
+    }
+    return 1;
+}
+
+static PyObject *
+StaticTuple_new_constructor(PyTypeObject *type, PyObject *args, PyObject *kwds)
+{
+    StaticTuple *self;
+    PyObject *obj = NULL;
+    Py_ssize_t i, len = 0;
+
+    if (type != &StaticTuple_Type) {
+        PyErr_SetString(PyExc_TypeError, "we only support creating StaticTuple");
+        return NULL;
+    }
+    if (!PyTuple_CheckExact(args)) {
+        PyErr_SetString(PyExc_TypeError, "args must be a tuple");
+        return NULL;
+    }
+    len = PyTuple_GET_SIZE(args);
+    if (len < 0 || len > 255) {
+        /* Check the length here so we can raise a TypeError instead of
+         * StaticTuple_New's ValueError.
+         */
+        PyErr_SetString(PyExc_TypeError, "StaticTuple(...)"
+            " takes from 0 to 255 items");
+        return NULL;
+    }
+    self = (StaticTuple *)StaticTuple_New(len);
+    if (self == NULL) {
+        return NULL;
+    }
+    for (i = 0; i < len; ++i) {
+        obj = PyTuple_GET_ITEM(args, i);
+        Py_INCREF(obj);
+        self->items[i] = obj;
+    }
+    if (!StaticTuple_check_items(self)) {
+        type->tp_dealloc((PyObject *)self);
+        return NULL;
+    }
+    return (PyObject *)self;
+}
+
+static PyObject *
+StaticTuple_repr(StaticTuple *self)
+{
+    PyObject *as_tuple, *tuple_repr, *result;
+
+    as_tuple = StaticTuple_as_tuple(self);
+    if (as_tuple == NULL) {
+        return NULL;
+    }
+    tuple_repr = PyObject_Repr(as_tuple);
+    Py_DECREF(as_tuple);
+    if (tuple_repr == NULL) {
+        return NULL;
+    }
+    result = PyString_FromFormat("StaticTuple%s",
+                                 PyString_AsString(tuple_repr));
+    return result;
+}
+
+static long
+StaticTuple_hash(StaticTuple *self)
+{
+    /* adapted from tuplehash(), is the specific hash value considered
+     * 'stable'?
+     */
+    register long x, y;
+    Py_ssize_t len = self->size;
+    PyObject **p;
+    long mult = 1000003L;
+
+#if STATIC_TUPLE_HAS_HASH
+    if (self->hash != -1) {
+        return self->hash;
+    }
+#endif
+    x = 0x345678L;
+    p = self->items;
+    // TODO: We could set specific flags if we know that, for example, all the
+    //       items are strings. I haven't seen a real-world benefit to that
+    //       yet, though.
+    while (--len >= 0) {
+        y = PyObject_Hash(*p++);
+        if (y == -1) /* failure */
+            return -1;
+        x = (x ^ y) * mult;
+        /* the cast might truncate len; that doesn't change hash stability */
+        mult += (long)(82520L + len + len);
+    }
+    x += 97531L;
+    if (x == -1)
+        x = -2;
+#if STATIC_TUPLE_HAS_HASH
+    self->hash = x;
+#endif
+    return x;
+}
+
+static PyObject *
+StaticTuple_richcompare_to_tuple(StaticTuple *v, PyObject *wt, int op)
+{
+    PyObject *vt;
+    PyObject *result = NULL;
+    
+    vt = StaticTuple_as_tuple((StaticTuple *)v);
+    if (vt == NULL) {
+        goto done;
+    }
+    if (!PyTuple_Check(wt)) {
+        PyErr_BadInternalCall();
+        goto done;
+    }
+    /* Now we have 2 tuples to compare, do it */
+    result = PyTuple_Type.tp_richcompare(vt, wt, op);
+done:
+    Py_XDECREF(vt);
+    return result;
+}
+
+/** Compare two objects to determine if they are equivalent.
+ * The basic flow is as follows
+ *  1) First make sure that both objects are StaticTuple instances. If they
+ *     aren't then cast self to a tuple, and have the tuple do the comparison.
+ *  2) Special case comparison to Py_None, because it happens to occur fairly
+ *     often in the test suite.
+ *  3) Special case when v and w are the same pointer. As we know the answer to
+ *     all queries without walking individual items.
+ *  4) For all operations, we then walk the items to find the first paired
+ *     items that are not equal.
+ *  5) If all items found are equal, we then check the length of self and
+ *     other to determine equality.
+ *  6) If an item differs, then we apply "op" to those last two items. (eg.
+ *     StaticTuple(A, B) > StaticTuple(A, C) iff B > C)
+ */
+
+static PyObject *
+StaticTuple_richcompare(PyObject *v, PyObject *w, int op)
+{
+    StaticTuple *v_st, *w_st;
+    Py_ssize_t vlen, wlen, min_len, i;
+    PyObject *v_obj, *w_obj;
+    richcmpfunc string_richcompare;
+
+    if (!StaticTuple_CheckExact(v)) {
+        /* This has never triggered, according to python-dev it seems this
+         * might trigger if '__op__' is defined but '__rop__' is not, sort of
+         * case. Such as "None == StaticTuple()"
+         */
+        fprintf(stderr, "self is not StaticTuple\n");
+        Py_INCREF(Py_NotImplemented);
+        return Py_NotImplemented;
+    }
+    v_st = (StaticTuple *)v;
+    if (StaticTuple_CheckExact(w)) {
+        /* The most common case */
+        w_st = (StaticTuple*)w;
+    } else if (PyTuple_Check(w)) {
+        /* One of v or w is a tuple, so we go the 'slow' route and cast up to
+         * tuples to compare.
+         */
+        /* TODO: This seems to be triggering more than I thought it would...
+         *       We probably want to optimize comparing self to other when
+         *       other is a tuple.
+         */
+        return StaticTuple_richcompare_to_tuple(v_st, w, op);
+    } else if (w == Py_None) {
+        // None is always less than the object
+        switch (op) {
+        case Py_NE:case Py_GT:case Py_GE:
+            Py_INCREF(Py_True);
+            return Py_True;
+        case Py_EQ:case Py_LT:case Py_LE:
+            Py_INCREF(Py_False);
+            return Py_False;
+    default: // Should never happen
+        return Py_NotImplemented;
+        }
+    } else {
+        /* We don't special case this comparison, we just let python handle
+         * it.
+         */
+         Py_INCREF(Py_NotImplemented);
+         return Py_NotImplemented;
+    }
+    /* Now we know that we have 2 StaticTuple objects, so let's compare them.
+     * This code is inspired from tuplerichcompare, except we know our
+     * objects are limited in scope, so we can inline some comparisons.
+     */
+    if (v == w) {
+        /* Identical pointers, we can shortcut this easily. */
+        switch (op) {
+        case Py_EQ:case Py_LE:case Py_GE:
+            Py_INCREF(Py_True);
+            return Py_True;
+        case Py_NE:case Py_LT:case Py_GT:
+            Py_INCREF(Py_False);
+            return Py_False;
+        }
+    }
+    if (op == Py_EQ
+        && _StaticTuple_is_interned(v_st)
+        && _StaticTuple_is_interned(w_st))
+    {
+        /* If both objects are interned, we know they are different if the
+         * pointer is not the same, which would have been handled by the
+         * previous if. No need to compare the entries.
+         */
+        Py_INCREF(Py_False);
+        return Py_False;
+    }
+
+    /* The only time we are likely to compare items of different lengths is in
+     * something like the interned_keys set. However, the hash is good enough
+     * that it is rare. Note that 'tuple_richcompare' also does not compare
+     * lengths here.
+     */
+    vlen = v_st->size;
+    wlen = w_st->size;
+    min_len = (vlen < wlen) ? vlen : wlen;
+    string_richcompare = PyString_Type.tp_richcompare;
+    for (i = 0; i < min_len; i++) {
+        PyObject *result = NULL;
+        v_obj = StaticTuple_GET_ITEM(v_st, i);
+        w_obj = StaticTuple_GET_ITEM(w_st, i);
+        if (v_obj == w_obj) {
+            /* Shortcut case, these must be identical */
+            continue;
+        }
+        if (PyString_CheckExact(v_obj) && PyString_CheckExact(w_obj)) {
+            result = string_richcompare(v_obj, w_obj, Py_EQ);
+        } else if (StaticTuple_CheckExact(v_obj) &&
+                   StaticTuple_CheckExact(w_obj))
+        {
+            /* Both are StaticTuple types, so recurse */
+            result = StaticTuple_richcompare(v_obj, w_obj, Py_EQ);
+        } else {
+            /* Fall back to generic richcompare */
+            result = PyObject_RichCompare(v_obj, w_obj, Py_EQ);
+        }
+        if (result == NULL) {
+            return NULL; /* There seems to be an error */
+        }
+        if (result == Py_False) {
+            // This entry is not identical, Shortcut for Py_EQ
+            if (op == Py_EQ) {
+                return result;
+            }
+            Py_DECREF(result);
+            break;
+        }
+        if (result != Py_True) {
+            /* We don't know *what* richcompare is returning, but it
+             * isn't something we recognize
+             */
+            PyErr_BadInternalCall();
+            Py_DECREF(result);
+            return NULL;
+        }
+        Py_DECREF(result);
+    }
+    if (i >= min_len) {
+        /* We walked off one of the lists, but everything compared equal so
+         * far. Just compare the size.
+         */
+        int cmp;
+        PyObject *res;
+        switch (op) {
+        case Py_LT: cmp = vlen <  wlen; break;
+        case Py_LE: cmp = vlen <= wlen; break;
+        case Py_EQ: cmp = vlen == wlen; break;
+        case Py_NE: cmp = vlen != wlen; break;
+        case Py_GT: cmp = vlen >  wlen; break;
+        case Py_GE: cmp = vlen >= wlen; break;
+        default: return NULL; /* cannot happen */
+        }
+        if (cmp)
+            res = Py_True;
+        else
+            res = Py_False;
+        Py_INCREF(res);
+        return res;
+    }
+    /* The last item differs, shortcut the Py_NE case */
+    if (op == Py_NE) {
+        Py_INCREF(Py_True);
+        return Py_True;
+    }
+    /* It is some other comparison, go ahead and do the real check. */
+    if (PyString_CheckExact(v_obj) && PyString_CheckExact(w_obj))
+    {
+        return string_richcompare(v_obj, w_obj, op);
+    } else if (StaticTuple_CheckExact(v_obj) &&
+               StaticTuple_CheckExact(w_obj))
+    {
+        /* Both are StaticTuple types, so recurse */
+        return StaticTuple_richcompare(v_obj, w_obj, op);
+    } else {
+        return PyObject_RichCompare(v_obj, w_obj, op);
+    }
+}
+
+
+static Py_ssize_t
+StaticTuple_length(StaticTuple *self)
+{
+    return self->size;
+}
+
+
+static PyObject *
+StaticTuple__is_interned(StaticTuple *self)
+{
+    if (_StaticTuple_is_interned(self)) {
+        Py_INCREF(Py_True);
+        return Py_True;
+    }
+    Py_INCREF(Py_False);
+    return Py_False;
+}
+
+static char StaticTuple__is_interned_doc[] = "_is_interned() => True/False\n"
+    "Check to see if this tuple has been interned.\n";
+
+
+static PyObject *
+StaticTuple_reduce(StaticTuple *self)
+{
+    PyObject *result = NULL, *as_tuple = NULL;
+
+    result = PyTuple_New(2);
+    if (!result) {
+        return NULL;
+    }
+    as_tuple = StaticTuple_as_tuple(self);
+    if (as_tuple == NULL) {
+        Py_DECREF(result);
+        return NULL;
+    }
+    Py_INCREF(&StaticTuple_Type);
+    PyTuple_SET_ITEM(result, 0, (PyObject *)&StaticTuple_Type);
+    PyTuple_SET_ITEM(result, 1, as_tuple);
+    return result;
+}
+
+static char StaticTuple_reduce_doc[] = "__reduce__() => tuple\n";
+
+
+static PyObject *
+StaticTuple_add(PyObject *v, PyObject *w)
+{
+    Py_ssize_t i, len_v, len_w;
+    PyObject *item;
+    StaticTuple *result;
+     /* StaticTuples and plain tuples may be added (concatenated) to
+      * StaticTuples.
+      */
+    if (StaticTuple_CheckExact(v)) {
+        len_v = ((StaticTuple*)v)->size;
+    } else if (PyTuple_Check(v)) {
+        len_v = PyTuple_GET_SIZE(v);
+    } else {
+        Py_INCREF(Py_NotImplemented);
+        return Py_NotImplemented;
+    }
+    if (StaticTuple_CheckExact(w)) {
+        len_w = ((StaticTuple*)w)->size;
+    } else if (PyTuple_Check(w)) {
+        len_w = PyTuple_GET_SIZE(w);
+    } else {
+        Py_INCREF(Py_NotImplemented);
+        return Py_NotImplemented;
+    }
+    result = StaticTuple_New(len_v + len_w);
+    if (result == NULL)
+        return NULL;
+    for (i = 0; i < len_v; ++i) {
+        // This returns a new reference, which we then 'steal' with 
+        // StaticTuple_SET_ITEM
+        item = PySequence_GetItem(v, i);
+        if (item == NULL) {
+            Py_DECREF(result);
+            return NULL;
+        }
+        StaticTuple_SET_ITEM(result, i, item);
+    }
+    for (i = 0; i < len_w; ++i) {
+        item = PySequence_GetItem(w, i);
+        if (item == NULL) {
+            Py_DECREF(result);
+            return NULL;
+        }
+        StaticTuple_SET_ITEM(result, i+len_v, item);
+    }
+    if (!StaticTuple_check_items(result)) {
+        Py_DECREF(result);
+        return NULL;
+    }
+    return (PyObject *)result;
+}
+
+static PyObject *
+StaticTuple_item(StaticTuple *self, Py_ssize_t offset)
+{
+    PyObject *obj;
+    /* We cast to (int) to avoid worrying about whether Py_ssize_t is a
+     * long long, etc. offsets should never be >2**31 anyway.
+     */
+    if (offset < 0) {
+        PyErr_Format(PyExc_IndexError, "StaticTuple_item does not support"
+            " negative indices: %d\n", (int)offset);
+    } else if (offset >= self->size) {
+        PyErr_Format(PyExc_IndexError, "StaticTuple index out of range"
+            " %d >= %d", (int)offset, (int)self->size);
+        return NULL;
+    }
+    obj = (PyObject *)self->items[offset];
+    Py_INCREF(obj);
+    return obj;
+}
+
+static PyObject *
+StaticTuple_slice(StaticTuple *self, Py_ssize_t ilow, Py_ssize_t ihigh)
+{
+    PyObject *as_tuple, *result;
+
+    as_tuple = StaticTuple_as_tuple(self);
+    if (as_tuple == NULL) {
+        return NULL;
+    }
+    result = PyTuple_Type.tp_as_sequence->sq_slice(as_tuple, ilow, ihigh);
+    Py_DECREF(as_tuple);
+    return result;
+}
+
+static int
+StaticTuple_traverse(StaticTuple *self, visitproc visit, void *arg)
+{
+    Py_ssize_t i;
+    for (i = self->size; --i >= 0;) {
+        Py_VISIT(self->items[i]);
+    }
+    return 0;
+}
+
+static char StaticTuple_doc[] =
+    "C implementation of a StaticTuple structure."
+    "\n This is used as StaticTuple(item1, item2, item3)"
+    "\n This is similar to tuple, less flexible in what it"
+    "\n supports, but also lighter memory consumption."
+    "\n Note that the constructor mimics the () form of tuples"
+    "\n Rather than the 'tuple()' constructor."
+    "\n  eg. StaticTuple(a, b) == (a, b) == tuple((a, b))";
+
+static PyMethodDef StaticTuple_methods[] = {
+    {"as_tuple", (PyCFunction)StaticTuple_as_tuple, METH_NOARGS, StaticTuple_as_tuple_doc},
+    {"intern", (PyCFunction)StaticTuple_Intern, METH_NOARGS, StaticTuple_Intern_doc},
+    {"_is_interned", (PyCFunction)StaticTuple__is_interned, METH_NOARGS,
+     StaticTuple__is_interned_doc},
+    {"from_sequence", (PyCFunction)StaticTuple_from_sequence,
+     METH_STATIC | METH_VARARGS,
+     "Create a StaticTuple from a given sequence. This functions"
+     " the same as the tuple() constructor."},
+    {"__reduce__", (PyCFunction)StaticTuple_reduce, METH_NOARGS, StaticTuple_reduce_doc},
+    {NULL, NULL} /* sentinel */
+};
+
+
+static PyNumberMethods StaticTuple_as_number = {
+    (binaryfunc) StaticTuple_add,   /* nb_add */
+    0,                              /* nb_subtract */
+    0,                              /* nb_multiply */
+    0,                              /* nb_divide */
+    0,                              /* nb_remainder */
+    0,                              /* nb_divmod */
+    0,                              /* nb_power */
+    0,                              /* nb_negative */
+    0,                              /* nb_positive */
+    0,                              /* nb_absolute */
+    0,                              /* nb_nonzero */
+    0,                              /* nb_invert */
+    0,                              /* nb_lshift */
+    0,                              /* nb_rshift */
+    0,                              /* nb_and */
+    0,                              /* nb_xor */
+    0,                              /* nb_or */
+    0,                              /* nb_coerce */
+};
+    
+
+static PySequenceMethods StaticTuple_as_sequence = {
+    (lenfunc)StaticTuple_length,            /* sq_length */
+    0,                              /* sq_concat */
+    0,                              /* sq_repeat */
+    (ssizeargfunc)StaticTuple_item,         /* sq_item */
+    (ssizessizeargfunc)StaticTuple_slice,   /* sq_slice */
+    0,                              /* sq_ass_item */
+    0,                              /* sq_ass_slice */
+    0,                              /* sq_contains */
+};
+
+/* TODO: Implement StaticTuple_as_mapping.
+ *       The only thing we really want to support from there is mp_subscript,
+ *       so that we could support extended slicing (foo[::2]). Not worth it
+ *       yet, though.
+ */
+
+
+PyTypeObject StaticTuple_Type = {
+    PyObject_HEAD_INIT(NULL)
+    0,                                           /* ob_size */
+    "bzrlib._static_tuple_c.StaticTuple",        /* tp_name */
+    sizeof(StaticTuple),                         /* tp_basicsize */
+    sizeof(PyObject *),                          /* tp_itemsize */
+    (destructor)StaticTuple_dealloc,             /* tp_dealloc */
+    0,                                           /* tp_print */
+    0,                                           /* tp_getattr */
+    0,                                           /* tp_setattr */
+    0,                                           /* tp_compare */
+    (reprfunc)StaticTuple_repr,                  /* tp_repr */
+    &StaticTuple_as_number,                      /* tp_as_number */
+    &StaticTuple_as_sequence,                    /* tp_as_sequence */
+    0,                                           /* tp_as_mapping */
+    (hashfunc)StaticTuple_hash,                  /* tp_hash */
+    0,                                           /* tp_call */
+    0,                                           /* tp_str */
+    0,                                           /* tp_getattro */
+    0,                                           /* tp_setattro */
+    0,                                           /* tp_as_buffer */
+    /* Py_TPFLAGS_CHECKTYPES tells the number operations that they shouldn't
+     * try to 'coerce' but instead stuff like 'add' will check it arguments.
+     */
+    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES,  /* tp_flags*/
+    StaticTuple_doc,                             /* tp_doc */
+    /* gc.get_referents checks the IS_GC flag before it calls tp_traverse
+     * And we don't include this object in the garbage collector because we
+     * know it doesn't create cycles. However, 'meliae' will follow
+     * tp_traverse, even if the object isn't GC, and we want that.
+     */
+    (traverseproc)StaticTuple_traverse,          /* tp_traverse */
+    0,                                           /* tp_clear */
+    StaticTuple_richcompare,                     /* tp_richcompare */
+    0,                                           /* tp_weaklistoffset */
+    // without implementing tp_iter, Python will fall back to PySequence*
+    // which seems to work ok, we may need something faster/lighter in the
+    // future.
+    0,                                           /* tp_iter */
+    0,                                           /* tp_iternext */
+    StaticTuple_methods,                         /* tp_methods */
+    0,                                           /* tp_members */
+    0,                                           /* tp_getset */
+    0,                                           /* tp_base */
+    0,                                           /* tp_dict */
+    0,                                           /* tp_descr_get */
+    0,                                           /* tp_descr_set */
+    0,                                           /* tp_dictoffset */
+    0,                                           /* tp_init */
+    0,                                           /* tp_alloc */
+    StaticTuple_new_constructor,                 /* tp_new */
+};
+
+
+static PyMethodDef static_tuple_c_methods[] = {
+    {NULL, NULL}
+};
+
+
+static void
+setup_interned_tuples(PyObject *m)
+{
+    _interned_tuples = (PyObject *)SimpleSet_New();
+    if (_interned_tuples != NULL) {
+        Py_INCREF(_interned_tuples);
+        PyModule_AddObject(m, "_interned_tuples", _interned_tuples);
+    }
+}
+
+
+static void
+setup_empty_tuple(PyObject *m)
+{
+    StaticTuple *stuple;
+    if (_interned_tuples == NULL) {
+        fprintf(stderr, "You need to call setup_interned_tuples() before"
+                " setup_empty_tuple, because we intern it.\n");
+    }
+    // We need to create the empty tuple
+    stuple = (StaticTuple *)StaticTuple_New(0);
+    _empty_tuple = StaticTuple_Intern(stuple);
+    assert(_empty_tuple == stuple);
+    // At this point, refcnt is 2: 1 from New(), and 1 from the return from
+    // intern(). We will keep 1 for the _empty_tuple global, and use the other
+    // for the module reference.
+    PyModule_AddObject(m, "_empty_tuple", (PyObject *)_empty_tuple);
+}
+
+static int
+_StaticTuple_CheckExact(PyObject *obj)
+{
+    return StaticTuple_CheckExact(obj);
+}
+
+static void
+setup_c_api(PyObject *m)
+{
+    _export_function(m, "StaticTuple_New", StaticTuple_New,
+        "StaticTuple *(Py_ssize_t)");
+    _export_function(m, "StaticTuple_Intern", StaticTuple_Intern,
+        "StaticTuple *(StaticTuple *)");
+    _export_function(m, "StaticTuple_FromSequence", StaticTuple_FromSequence,
+        "StaticTuple *(PyObject *)");
+    _export_function(m, "_StaticTuple_CheckExact", _StaticTuple_CheckExact,
+        "int(PyObject *)");
+}
+
+
+static int
+_workaround_pyrex_096(void)
+{
+    /* Work around an incompatibility in how pyrex 0.9.6 exports a module,
+     * versus how pyrex 0.9.8 and cython 0.11 export it.
+     * Namely 0.9.6 exports import__simple_set_pyx and tries to
+     * "import _simple_set_pyx" but it is available only as
+     * "import bzrlib._simple_set_pyx"
+     * It is a shame to hack up sys.modules, but that is what we've got to do.
+     */
+    PyObject *sys_module = NULL, *modules = NULL, *set_module = NULL;
+    int retval = -1;
+
+    /* Clear out the current ImportError exception, and try again. */
+    PyErr_Clear();
+    /* Note that this only seems to work if somewhere else imports
+     * bzrlib._simple_set_pyx before importing bzrlib._static_tuple_c
+     */
+    set_module = PyImport_ImportModule("bzrlib._simple_set_pyx");
+    if (set_module == NULL) {
+        goto end;
+    }
+    /* Add the _simple_set_pyx into sys.modules at the appropriate location. */
+    sys_module = PyImport_ImportModule("sys");
+    if (sys_module == NULL) {
+        goto end;
+    }
+    modules = PyObject_GetAttrString(sys_module, "modules");
+    if (modules == NULL || !PyDict_Check(modules)) {
+        goto end;
+    }
+    PyDict_SetItemString(modules, "_simple_set_pyx", set_module);
+    /* Now that we have hacked it in, try the import again. */
+    retval = import_bzrlib___simple_set_pyx();
+end:
+    Py_XDECREF(set_module);
+    Py_XDECREF(sys_module);
+    Py_XDECREF(modules);
+    return retval;
+}
+
+
+PyMODINIT_FUNC
+init_static_tuple_c(void)
+{
+    PyObject* m;
+
+    StaticTuple_Type.tp_getattro = PyObject_GenericGetAttr;
+    if (PyType_Ready(&StaticTuple_Type) < 0)
+        return;
+
+    m = Py_InitModule3("_static_tuple_c", static_tuple_c_methods,
+                       "C implementation of a StaticTuple structure");
+    if (m == NULL)
+      return;
+
+    Py_INCREF(&StaticTuple_Type);
+    PyModule_AddObject(m, "StaticTuple", (PyObject *)&StaticTuple_Type);
+    if (import_bzrlib___simple_set_pyx() == -1
+        && _workaround_pyrex_096() == -1)
+    {
+        return;
+    }
+    setup_interned_tuples(m);
+    setup_empty_tuple(m);
+    setup_c_api(m);
+}
+
+// vim: tabstop=4 sw=4 expandtab

=== added file 'bzrlib/_static_tuple_c.h'
--- bzrlib/_static_tuple_c.h	1970-01-01 00:00:00 +0000
+++ bzrlib/_static_tuple_c.h	2010-02-18 00:00:51 +0000
@@ -0,0 +1,116 @@
+/* Copyright (C) 2009 Canonical Ltd
+ * 
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _STATIC_TUPLE_H_
+#define _STATIC_TUPLE_H_
+#include <Python.h>
+#include <string.h>
+
+#define STATIC_TUPLE_HAS_HASH 0
+/* Caching the hash adds memory, but allows us to save a little time during
+ * lookups. TIMEIT hash(key) shows it as
+ *  0.108usec w/ hash
+ *  0.160usec w/o hash
+ * Note that the entries themselves are strings, which already cache their
+ * hashes. So while there is a 1.5:1 difference in the time for hash(), it is
+ * already a function which is quite fast. Probably the only reason we might
+ * want to do so, is if we customized SimpleSet to the point that the item
+ * pointers were exactly certain types, and then accessed table[i]->hash
+ * directly. So far StaticTuple_hash() is fast enough to not warrant the memory
+ * difference.
+ */
+
+/* This defines a single variable-width key.
+ * It is basically the same as a tuple, but
+ * 1) Lighter weight in memory
+ * 2) Only supports strings or other static types (that don't reference other
+ *    objects.)
+ */
+
+#define STATIC_TUPLE_INTERNED_FLAG 0x01
+typedef struct {
+    PyObject_HEAD
+    // We could go with unsigned short here, and support 64k width tuples
+    // without any memory impact, might be worthwhile
+    unsigned char size;
+    unsigned char flags;
+    unsigned char _unused0;
+    unsigned char _unused1;
+    // Note that on 64-bit, we actually have 4-more unused bytes
+    // because items will always be aligned to a 64-bit boundary
+#if STATIC_TUPLE_HAS_HASH
+    long hash;
+#endif
+    PyObject *items[0];
+} StaticTuple;
+extern PyTypeObject StaticTuple_Type;
+
+typedef struct {
+    PyObject_VAR_HEAD
+    PyObject *table[0];
+} KeyIntern;
+
+#define StaticTuple_SET_ITEM(key, offset, val) \
+    ((((StaticTuple*)(key))->items[(offset)]) = ((PyObject *)(val)))
+#define StaticTuple_GET_ITEM(key, offset) (((StaticTuple*)key)->items[offset])
+
+
+#ifdef STATIC_TUPLE_MODULE
+/* Used when compiling _static_tuple_c.c */
+
+static StaticTuple * StaticTuple_New(Py_ssize_t);
+static StaticTuple * StaticTuple_Intern(StaticTuple *self);
+static StaticTuple * StaticTuple_FromSequence(PyObject *);
+#define StaticTuple_CheckExact(op) (Py_TYPE(op) == &StaticTuple_Type)
+
+#else
+/* Used as the foreign api */
+
+#include "_import_c_api.h"
+
+static StaticTuple *(*StaticTuple_New)(Py_ssize_t);
+static StaticTuple *(*StaticTuple_Intern)(StaticTuple *);
+static StaticTuple *(*StaticTuple_FromSequence)(PyObject *);
+static PyTypeObject *_p_StaticTuple_Type;
+
+#define StaticTuple_CheckExact(op) (Py_TYPE(op) == _p_StaticTuple_Type)
+static int (*_StaticTuple_CheckExact)(PyObject *);
+
+
+/* Return -1 and set exception on error, 0 on success */
+static int
+import_static_tuple_c(void)
+{
+    struct function_description functions[] = {
+        {"StaticTuple_New", (void **)&StaticTuple_New,
+            "StaticTuple *(Py_ssize_t)"},
+        {"StaticTuple_Intern", (void **)&StaticTuple_Intern,
+            "StaticTuple *(StaticTuple *)"},
+        {"StaticTuple_FromSequence", (void **)&StaticTuple_FromSequence,
+            "StaticTuple *(PyObject *)"},
+        {"_StaticTuple_CheckExact", (void **)&_StaticTuple_CheckExact,
+            "int(PyObject *)"},
+        {NULL}};
+    struct type_description types[] = {
+        {"StaticTuple", &_p_StaticTuple_Type},
+        {NULL}};
+    return _import_extension_module("bzrlib._static_tuple_c",
+        functions, types);
+}
+
+#endif // !STATIC_TUPLE_MODULE
+#endif // !_STATIC_TUPLE_H_

=== added file 'bzrlib/_static_tuple_c.pxd'
--- bzrlib/_static_tuple_c.pxd	1970-01-01 00:00:00 +0000
+++ bzrlib/_static_tuple_c.pxd	2010-02-18 00:00:51 +0000
@@ -0,0 +1,44 @@
+# Copyright (C) 2009, 2010 Canonical Ltd
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+"""The interface definition file for the StaticTuple class."""
+
+
+cdef extern from "Python.h":
+    ctypedef int Py_ssize_t # Required for older pyrex versions
+    ctypedef struct PyObject:
+        pass
+
+cdef extern from "_static_tuple_c.h":
+    ctypedef class bzrlib._static_tuple_c.StaticTuple [object StaticTuple]:
+        cdef unsigned char size
+        cdef unsigned char flags
+        cdef PyObject *items[0]
+
+    # Must be called before using any of the C api, as it sets the function
+    # pointers in memory.
+    int import_static_tuple_c() except -1
+    StaticTuple StaticTuple_New(Py_ssize_t)
+    StaticTuple StaticTuple_Intern(StaticTuple)
+
+    # Steals a reference and val must be a valid type, no checking is done
+    void StaticTuple_SET_ITEM(StaticTuple key, Py_ssize_t offset, object val)
+    # We would normally use PyObject * here. However it seems that cython/pyrex
+    # treat the PyObject defined in this header as something different than one
+    # defined in a .pyx file. And since we don't INCREF, we need a raw pointer,
+    # not an 'object' return value.
+    void *StaticTuple_GET_ITEM(StaticTuple key, Py_ssize_t offset)
+    int StaticTuple_CheckExact(object)

=== added file 'bzrlib/_static_tuple_py.py'
--- bzrlib/_static_tuple_py.py	1970-01-01 00:00:00 +0000
+++ bzrlib/_static_tuple_py.py	2010-02-18 00:00:52 +0000
@@ -0,0 +1,80 @@
+# Copyright (C) 2009, 2010 Canonical Ltd
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+"""The pure-python implementation of the StaticTuple type.
+
+Note that it is generally just implemented as using tuples of tuples of
+strings.
+"""
+
+
+class StaticTuple(tuple):
+    """A static type, similar to a tuple of strings."""
+
+    __slots__ = ()
+
+    def __new__(cls, *args):
+        # Make the empty StaticTuple a singleton
+        if not args and _empty_tuple is not None:
+            return _empty_tuple
+        return tuple.__new__(cls, args)
+
+    def __init__(self, *args):
+        """Create a new 'StaticTuple'"""
+        num_keys = len(args)
+        if num_keys < 0 or num_keys > 255:
+            raise TypeError('StaticTuple(...) takes from 0 to 255 items')
+        for bit in args:
+            if type(bit) not in (str, StaticTuple, unicode, int, long, float,
+                                 None.__class__, bool):
+                raise TypeError('StaticTuple can only point to'
+                    ' StaticTuple, str, unicode, int, long, float, bool, or'
+                    ' None not %s' % (type(bit),))
+        # We don't need to pass args to tuple.__init__, because that was
+        # already handled in __new__.
+        tuple.__init__(self)
+
+    def __repr__(self):
+        return '%s%s' % (self.__class__.__name__, tuple.__repr__(self))
+
+    def __reduce__(self):
+        return (StaticTuple, tuple(self))
+
+    def __add__(self, other):
+        """Concatenate self with other"""
+        return StaticTuple.from_sequence(tuple.__add__(self,other))
+
+    def as_tuple(self):
+        return tuple(self)
+
+    def intern(self):
+        return _interned_tuples.setdefault(self, self)
+
+    @staticmethod
+    def from_sequence(seq):
+        """Convert a sequence object into a StaticTuple instance."""
+        if isinstance(seq, StaticTuple):
+            # it already is
+            return seq
+        return StaticTuple(*seq)
+
+
+
+# Have to set it to None first, so that __new__ can determine whether
+# the _empty_tuple singleton has been created yet or not.
+_empty_tuple = None
+_empty_tuple = StaticTuple()
+_interned_tuples = {}

=== modified file 'bzrlib/_walkdirs_win32.pyx'
--- bzrlib/_walkdirs_win32.pyx	2010-01-05 04:59:57 +0000
+++ bzrlib/_walkdirs_win32.pyx	2010-02-18 00:00:51 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2008 Canonical Ltd
+# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by

=== modified file 'bzrlib/annotate.py'
--- bzrlib/annotate.py	2009-08-17 18:52:01 +0000
+++ bzrlib/annotate.py	2010-02-18 00:00:51 +0000
@@ -458,5 +458,6 @@
 
 try:
     from bzrlib._annotator_pyx import Annotator
-except ImportError:
+except ImportError, e:
+    osutils.failed_to_load_extension(e)
     from bzrlib._annotator_py import Annotator

=== modified file 'bzrlib/benchmarks/bench_dirstate.py'
--- bzrlib/benchmarks/bench_dirstate.py	2009-06-22 15:39:42 +0000
+++ bzrlib/benchmarks/bench_dirstate.py	2010-02-18 00:00:52 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2007 Canonical Ltd
+# Copyright (C) 2007, 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -26,7 +26,7 @@
     tests,
     )
 from bzrlib.tests.test__dirstate_helpers import (
-    CompiledDirstateHelpersFeature,
+    compiled_dirstate_helpers_feature,
     )
 
 
@@ -206,7 +206,7 @@
             state.unlock()
 
     def test__read_dirblocks_20k_tree_0_parents_pyx(self):
-        self.requireFeature(CompiledDirstateHelpersFeature)
+        self.requireFeature(compiled_dirstate_helpers_feature)
         from bzrlib._dirstate_helpers_pyx import _read_dirblocks
         state = self.build_20k_dirstate()
         state.lock_read()
@@ -231,7 +231,7 @@
             state.unlock()
 
     def test__read_dirblocks_20k_tree_1_parent_pyx(self):
-        self.requireFeature(CompiledDirstateHelpersFeature)
+        self.requireFeature(compiled_dirstate_helpers_feature)
         from bzrlib._dirstate_helpers_pyx import _read_dirblocks
         state = self.build_20k_dirstate_with_parents(1)
         state.lock_read()
@@ -256,7 +256,7 @@
             state.unlock()
 
     def test__read_dirblocks_20k_tree_2_parents_pyx(self):
-        self.requireFeature(CompiledDirstateHelpersFeature)
+        self.requireFeature(compiled_dirstate_helpers_feature)
         from bzrlib._dirstate_helpers_pyx import _read_dirblocks
         state = self.build_20k_dirstate_with_parents(2)
         state.lock_read()
@@ -337,7 +337,7 @@
             state.unlock()
 
     def test_bisect_dirblock_pyx(self):
-        self.requireFeature(CompiledDirstateHelpersFeature)
+        self.requireFeature(compiled_dirstate_helpers_feature)
         from bzrlib._dirstate_helpers_pyx import bisect_dirblock
         state = self.build_10k_dirstate_dirs()
         state.lock_read()
@@ -420,7 +420,7 @@
                              [(3, 1), (3, 1), (3, 1), (3, 2)])
 
     def test_cmp_by_dirs_pyrex(self):
-        self.requireFeature(CompiledDirstateHelpersFeature)
+        self.requireFeature(compiled_dirstate_helpers_feature)
         from bzrlib._dirstate_helpers_pyx import cmp_by_dirs
         self.compareAllPaths(cmp_by_dirs,
                              [(3, 1), (3, 1), (3, 1), (3, 2)])

=== modified file 'bzrlib/bencode.py'
--- bzrlib/bencode.py	2009-06-03 14:14:31 +0000
+++ bzrlib/bencode.py	2010-02-18 00:00:52 +0000
@@ -16,7 +16,10 @@
 
 """Wrapper around the bencode pyrex and python implementation"""
 
+from bzrlib import osutils
+
 try:
     from bzrlib._bencode_pyx import bdecode, bdecode_as_tuple, bencode, Bencached
-except ImportError:
+except ImportError, e:
+    osutils.failed_to_load_extension(e)
     from bzrlib.util._bencode_py import bdecode, bdecode_as_tuple, bencode, Bencached

=== modified file 'bzrlib/branch.py'
--- bzrlib/branch.py	2009-11-23 07:10:47 +0000
+++ bzrlib/branch.py	2010-02-18 00:00:52 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2005, 2006, 2007, 2008, 2009 Canonical Ltd
+# Copyright (C) 2005-2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -46,9 +46,10 @@
     )
 """)
 
-from bzrlib.decorators import needs_read_lock, needs_write_lock
+from bzrlib.decorators import needs_read_lock, needs_write_lock, only_raises
 from bzrlib.hooks import HookPoint, Hooks
 from bzrlib.inter import InterObject
+from bzrlib.lock import _RelockDebugMixin
 from bzrlib import registry
 from bzrlib.symbol_versioning import (
     deprecated_in,
@@ -502,12 +503,25 @@
                 left_parent = stop_rev.parent_ids[0]
             else:
                 left_parent = _mod_revision.NULL_REVISION
+            # left_parent is the actual revision we want to stop logging at,
+            # since we want to show the merged revisions after the stop_rev too
+            reached_stop_revision_id = False
+            revision_id_whitelist = []
             for node in rev_iter:
                 rev_id = node.key[-1]
                 if rev_id == left_parent:
+                    # reached the left parent after the stop_revision
                     return
-                yield (rev_id, node.merge_depth, node.revno,
+                if (not reached_stop_revision_id or
+                        rev_id in revision_id_whitelist):
+                    yield (rev_id, node.merge_depth, node.revno,
                        node.end_of_merge)
+                    if reached_stop_revision_id or rev_id == stop_revision_id:
+                        # only do the merged revs of rev_id from now on
+                        rev = self.repository.get_revision(rev_id)
+                        if rev.parent_ids:
+                            reached_stop_revision_id = True
+                            revision_id_whitelist.extend(rev.parent_ids)
         else:
             raise ValueError('invalid stop_rule %r' % stop_rule)
 
@@ -1089,15 +1103,7 @@
         params = ChangeBranchTipParams(
             self, old_revno, new_revno, old_revid, new_revid)
         for hook in hooks:
-            try:
-                hook(params)
-            except errors.TipChangeRejected:
-                raise
-            except Exception:
-                exc_info = sys.exc_info()
-                hook_name = Branch.hooks.get_hook_name(hook)
-                raise errors.HookFailed(
-                    'pre_change_branch_tip', hook_name, exc_info)
+            hook(params)
 
     @needs_write_lock
     def update(self):
@@ -1432,10 +1438,10 @@
         """Return the format for the branch object in a_bzrdir."""
         try:
             transport = a_bzrdir.get_branch_transport(None)
-            format_string = transport.get("format").read()
+            format_string = transport.get_bytes("format")
             return klass._formats[format_string]
         except errors.NoSuchFile:
-            raise errors.NotBranchError(path=transport.base)
+            raise errors.NotBranchError(path=transport.base, bzrdir=a_bzrdir)
         except KeyError:
             raise errors.UnknownFormatError(format=format_string, kind='branch')
 
@@ -1790,7 +1796,7 @@
                               _repository=a_bzrdir.find_repository(),
                               ignore_fallbacks=ignore_fallbacks)
         except errors.NoSuchFile:
-            raise errors.NotBranchError(path=transport.base)
+            raise errors.NotBranchError(path=transport.base, bzrdir=a_bzrdir)
 
     def __init__(self):
         super(BranchFormatMetadir, self).__init__()
@@ -1971,7 +1977,7 @@
     def get_reference(self, a_bzrdir):
         """See BranchFormat.get_reference()."""
         transport = a_bzrdir.get_branch_transport(None)
-        return transport.get('location').read()
+        return transport.get_bytes('location')
 
     def set_reference(self, a_bzrdir, to_branch):
         """See BranchFormat.set_reference()."""
@@ -2072,7 +2078,7 @@
     _legacy_formats[0].network_name(), _legacy_formats[0].__class__)
 
 
-class BzrBranch(Branch):
+class BzrBranch(Branch, _RelockDebugMixin):
     """A branch stored in the actual filesystem.
 
     Note that it's "local" in the context of the filesystem; it doesn't
@@ -2124,9 +2130,12 @@
         return self.control_files.is_locked()
 
     def lock_write(self, token=None):
+        if not self.is_locked():
+            self._note_lock('w')
         # All-in-one needs to always unlock/lock.
         repo_control = getattr(self.repository, 'control_files', None)
         if self.control_files == repo_control or not self.is_locked():
+            self.repository._warn_if_deprecated(self)
             self.repository.lock_write()
             took_lock = True
         else:
@@ -2139,9 +2148,12 @@
             raise
 
     def lock_read(self):
+        if not self.is_locked():
+            self._note_lock('r')
         # All-in-one needs to always unlock/lock.
         repo_control = getattr(self.repository, 'control_files', None)
         if self.control_files == repo_control or not self.is_locked():
+            self.repository._warn_if_deprecated(self)
             self.repository.lock_read()
             took_lock = True
         else:
@@ -2153,6 +2165,7 @@
                 self.repository.unlock()
             raise
 
+    @only_raises(errors.LockNotHeld, errors.LockBroken)
     def unlock(self):
         try:
             self.control_files.unlock()

=== modified file 'bzrlib/btree_index.py'
--- bzrlib/btree_index.py	2009-09-09 19:32:27 +0000
+++ bzrlib/btree_index.py	2010-02-18 00:00:50 +0000
@@ -1,4 +1,4 @@
-# Copyright (C) 2008 Canonical Ltd
+# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 #
 # This program is free software; you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -17,6 +17,7 @@
 
 """B+Tree indices"""
 
+import cStringIO
 from bisect import bisect_right
 import math
 import tempfile
@@ -30,6 +31,7 @@
     index,
     lru_cache,
     osutils,
+    static_tuple,
     trace,
     )
 from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
@@ -60,14 +62,20 @@
     def __init__(self):
         """Create a _BuilderRow."""
         self.nodes = 0
-        self.spool = tempfile.TemporaryFile()
+        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
         self.writer = None
 
     def finish_node(self, pad=True):
         byte_lines, _, padding = self.writer.finish()
         if self.nodes == 0:
+            self.spool = cStringIO.StringIO()
             # padded note:
             self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
+        elif self.nodes == 1:
+            # We got bigger than 1 node, switch to a temp file
+            spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
+            spool.write(self.spool.getvalue())
+            self.spool = spool