Rev 3734: Various docs towards a new inventory design. in file:///home/pqm/archives/thelove/bzr/%2Btrunk/
Canonical.com Patch Queue Manager
pqm at pqm.ubuntu.com
Wed Sep 24 09:15:43 BST 2008
At file:///home/pqm/archives/thelove/bzr/%2Btrunk/
------------------------------------------------------------
revno: 3734
revision-id: pqm at pqm.ubuntu.com-20080924081540-ecfvp6xq4x9gs81n
parent: pqm at pqm.ubuntu.com-20080924072647-hpc17iasylpwiaem
parent: robertc at robertcollins.net-20080924073356-dfg5qqbd7f74mwmt
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Wed 2008-09-24 09:15:40 +0100
message:
Various docs towards a new inventory design.
modified:
doc/developers/inventory.txt inventory.txt-20080103013957-opkrhxy6lmywmx4i-1
------------------------------------------------------------
revno: 3638.5.7
revision-id: robertc at robertcollins.net-20080924073356-dfg5qqbd7f74mwmt
parent: robertc at robertcollins.net-20080924071224-o4qqw838s6inr20c
committer: Robert Collins <robertc at robertcollins.net>
branch nick: inventory
timestamp: Wed 2008-09-24 17:33:56 +1000
message:
Work around ReST FAIL.
modified:
doc/developers/inventory.txt inventory.txt-20080103013957-opkrhxy6lmywmx4i-1
------------------------------------------------------------
revno: 3638.5.6
revision-id: robertc at robertcollins.net-20080924071224-o4qqw838s6inr20c
parent: robertc at robertcollins.net-20080924062744-shox2i6ks7fy110d
committer: Robert Collins <robertc at robertcollins.net>
branch nick: inventory
timestamp: Wed 2008-09-24 17:12:24 +1000
message:
Define CHK and very minor tweaks to the inventory text.
modified:
doc/developers/inventory.txt inventory.txt-20080103013957-opkrhxy6lmywmx4i-1
------------------------------------------------------------
revno: 3638.5.5
revision-id: robertc at robertcollins.net-20080924062744-shox2i6ks7fy110d
parent: robertc at robertcollins.net-20080828033752-6ry5zf5dxsnhibxg
parent: pqm at pqm.ubuntu.com-20080924014325-ucivgbdmsbuthnqw
committer: Robert Collins <robertc at robertcollins.net>
branch nick: inventory
timestamp: Wed 2008-09-24 16:27:44 +1000
message:
Merge dev.
removed:
tools/win32/survey.txt survey.txt-20070809075950-sf265mgu9oog8jjb-1
added:
bzrlib/_btree_serializer_c.pyx _parse_btree_c.pyx-20080703034413-3q25bklkenti3p8p-2
bzrlib/_btree_serializer_py.py _parse_btree_py.py-20080703034413-3q25bklkenti3p8p-3
bzrlib/_readdir_py.py readdir.py-20060609152855-rm6v321vuaqyh9tu-3
bzrlib/_readdir_pyx.pyx readdir.pyx-20060609152855-rm6v321vuaqyh9tu-1
bzrlib/btree_index.py index.py-20080624222253-p0x5f92uyh5hw734-7
bzrlib/chunk_writer.py chunk_writer.py-20080630234519-6ggn4id17nipovny-1
bzrlib/readdir.h readdir.h-20060609152855-rm6v321vuaqyh9tu-2
bzrlib/tests/test_btree_index.py test_index.py-20080624222253-p0x5f92uyh5hw734-13
bzrlib/tests/test_chunk_writer.py test_chunk_writer.py-20080630234519-6ggn4id17nipovny-2
bzrlib/tests/test_transport_log.py test_transport_log.p-20080902041816-vh8x5yt5nvdzvew3-3
bzrlib/transport/ftp/ ftp-20080611185801-3vm145h8dmnfgh25-1
bzrlib/transport/ftp/_gssapi.py _gssapi.py-20080611190840-7ejrtp884bk5eu72-2
bzrlib/transport/log.py log.py-20080902041816-vh8x5yt5nvdzvew3-5
doc/developers/overview.txt overview.txt-20080904022501-ww2ggomrs5elxfm0-1
tools/packaging/ packaging-20080825202834-3j433iaawnt72wqa-1
tools/packaging/build-packages.sh buildpackages.sh-20080821102059-fzlodktas65qmo1k-1
tools/packaging/update-changelogs.sh updatechangelogs.sh-20080821102059-fzlodktas65qmo1k-2
tools/packaging/update-packaging-branches.sh updatepackagingbranc-20080825210254-6is8ciit1yzyd3a2-1
renamed:
bzrlib/tests/repository_implementations => bzrlib/tests/per_repository repository_implementations-20060131092037-ec97814745cc6128
bzrlib/transport/ftp.py => bzrlib/transport/ftp/__init__.py ftp.py-20051116161804-58dc9506548c2a53
doc/en/developer-guide/testing.txt => doc/developers/testing.txt testing.txt-20080812140359-i70zzh6v2z7grqex-1
modified:
.bzrignore bzrignore-20050311232317-81f7b71efa2db11a
Makefile Makefile-20050805140406-d96e3498bb61c5bb
NEWS NEWS-20050323055033-4e00b5db738777ff
bzr bzr.py-20050313053754-5485f144c7006fa6
bzr.ico bzr.ico-20060629083000-q18ip0hk7lq55i4y-1
bzrlib/__init__.py __init__.py-20050309040759-33e65acf91bbcd5d
bzrlib/_dirstate_helpers_c.pyx dirstate_helpers.pyx-20070503201057-u425eni465q4idwn-3
bzrlib/_dirstate_helpers_py.py _dirstate_helpers_py-20070710145033-90nz6cqglsk150jy-1
bzrlib/_patiencediff_c.c _patiencediff_c.c-20070721205602-q3imkipwlgagp3cy-1
bzrlib/_walkdirs_win32.pyx _walkdirs_win32.pyx-20080716220454-kweh3tgxez5dvw2l-2
bzrlib/annotate.py annotate.py-20050922133147-7c60541d2614f022
bzrlib/atomicfile.py atomicfile.py-20050509044450-dbd24e6c564f7c66
bzrlib/benchmarks/bench_osutils.py bench_osutils.py-20060608153714-apso8cyz1bu2z1ig-1
bzrlib/branch.py branch.py-20050309040759-e4baf4e0d046576e
bzrlib/builtins.py builtins.py-20050830033751-fc01482b9ca23183
bzrlib/bundle/__init__.py changeset.py-20050513021216-b02ab57fb9738913
bzrlib/bundle/bundle_data.py read_changeset.py-20050619171944-c0d95aa685537640
bzrlib/bzrdir.py bzrdir.py-20060131065624-156dfea39c4387cb
bzrlib/commands.py bzr.py-20050309040720-d10f4714595cf8c3
bzrlib/config.py config.py-20051011043216-070c74f4e9e338e8
bzrlib/diff.py diff.py-20050309040759-26944fbbf2ebbf36
bzrlib/directory_service.py directory_service.py-20080305221044-vr2mkvlsk8jypa2y-1
bzrlib/errors.py errors.py-20050309040759-20512168c4e14fbd
bzrlib/fetch.py fetch.py-20050818234941-26fea6105696365d
bzrlib/help_topics/__init__.py help_topics.py-20060920210027-rnim90q9e0bwxvy4-1
bzrlib/help_topics/en/hooks.txt hooks.txt-20070830033044-xxu2rced13f72dka-1
bzrlib/hooks.py hooks.py-20070325015548-ix4np2q0kd8452au-1
bzrlib/index.py index.py-20070712131115-lolkarso50vjr64s-1
bzrlib/knit.py knit.py-20051212171256-f056ac8f0fbe1bd9
bzrlib/lock.py lock.py-20050527050856-ec090bb51bc03349
bzrlib/lockdir.py lockdir.py-20060220222025-98258adf27fbdda3
bzrlib/log.py log.py-20050505065812-c40ce11702fe5fb1
bzrlib/lsprof.py lsprof.py-20051208071030-833790916798ceed
bzrlib/mail_client.py mail_client.py-20070809192806-vuxt3t19srtpjpdn-1
bzrlib/memorytree.py memorytree.py-20060906023413-4wlkalbdpsxi2r4y-1
bzrlib/merge.py merge.py-20050513021216-953b65a438527106
bzrlib/missing.py missing.py-20050812153334-097f7097e2a8bcd1
bzrlib/option.py option.py-20051014052914-661fb36e76e7362f
bzrlib/osutils.py osutils.py-20050309040759-eeaff12fbf77ac86
bzrlib/plugin.py plugin.py-20050622060424-829b654519533d69
bzrlib/push.py push.py-20080606021927-5fe39050e8xne9un-1
bzrlib/reconcile.py reweave_inventory.py-20051108164726-1e5e0934febac06e
bzrlib/remote.py remote.py-20060720103555-yeeg2x51vn0rbtdp-1
bzrlib/repofmt/pack_repo.py pack_repo.py-20070813041115-gjv5ma7ktfqwsjgn-1
bzrlib/repository.py rev_storage.py-20051111201905-119e9401e46257e3
bzrlib/revisionspec.py revisionspec.py-20050907152633-17567659fd5c0ddb
bzrlib/smart/branch.py branch.py-20061124031907-mzh3pla28r83r97f-1
bzrlib/smart/client.py client.py-20061116014825-2k6ada6xgulslami-1
bzrlib/smart/medium.py medium.py-20061103051856-rgu2huy59fkz902q-1
bzrlib/smart/message.py message.py-20080222013625-ncqmh3nrxjkxab87-1
bzrlib/smart/protocol.py protocol.py-20061108035435-ot0lstk2590yqhzr-1
bzrlib/smart/repository.py repository.py-20061128022038-vr5wy5bubyb8xttk-1
bzrlib/smart/request.py request.py-20061108095550-gunadhxmzkdjfeek-1
bzrlib/smart/server.py server.py-20061110062051-chzu10y32vx8gvur-1
bzrlib/status.py status.py-20050505062338-431bfa63ec9b19e6
bzrlib/tests/__init__.py selftest.py-20050531073622-8d0e3c8845c97a64
bzrlib/tests/blackbox/test_annotate.py testannotate.py-20051013044000-457f44801bfa9d39
bzrlib/tests/blackbox/test_branch.py test_branch.py-20060524161337-noms9gmcwqqrfi8y-1
bzrlib/tests/blackbox/test_cat_revision.py test_cat_revision.py-20070410204634-fq8mnld5l5aza9e2-1
bzrlib/tests/blackbox/test_export.py test_export.py-20051229024010-e6c26658e460fb1c
bzrlib/tests/blackbox/test_info.py test_info.py-20060215045507-bbdd2d34efab9e0a
bzrlib/tests/blackbox/test_init.py test_init.py-20060309032856-a292116204d86eb7
bzrlib/tests/blackbox/test_log.py test_log.py-20060112090212-78f6ea560c868e24
bzrlib/tests/blackbox/test_merge.py test_merge.py-20060323225809-9bc0459c19917f41
bzrlib/tests/blackbox/test_missing.py test_missing.py-20051211212735-a2cf4c1840bb84c4
bzrlib/tests/blackbox/test_non_ascii.py test_non_ascii.py-20060105214030-68010be784a5d854
bzrlib/tests/blackbox/test_outside_wt.py test_outside_wt.py-20060116200058-98edd33e7db8bdde
bzrlib/tests/blackbox/test_push.py test_push.py-20060329002750-929af230d5d22663
bzrlib/tests/blackbox/test_remove_tree.py test_remove_tree.py-20061110192919-5j3xjciiaqbs2dvo-1
bzrlib/tests/blackbox/test_selftest.py test_selftest.py-20060123024542-01c5f1bbcb596d78
bzrlib/tests/blackbox/test_send.py test_bundle.py-20060616222707-c21c8b7ea5ef57b1
bzrlib/tests/blackbox/test_status.py teststatus.py-20050712014354-508855eb9f29f7dc
bzrlib/tests/blackbox/test_switch.py test_switch.py-20071122111948-0c5en6uz92bwl76h-1
bzrlib/tests/branch_implementations/test_break_lock.py test_break_lock.py-20060504111902-9aae411dbe9aadd2
bzrlib/tests/branch_implementations/test_hooks.py test_hooks.py-20070129154855-blhpwxmvjs07waei-1
bzrlib/tests/branch_implementations/test_locking.py test_locking.py-20060707151933-tav3o2hpibwi53u4-4
bzrlib/tests/branch_implementations/test_permissions.py test_permissions.py-20060210110243-245c01403bf0fde6
bzrlib/tests/branch_implementations/test_push.py test_push.py-20070130153159-fhfap8uoifevg30j-1
bzrlib/tests/bzrdir_implementations/test_bzrdir.py test_bzrdir.py-20060131065642-0ebeca5e30e30866
bzrlib/tests/intertree_implementations/__init__.py __init__.py-20060724101752-09ysswo1a92uqyoz-3
bzrlib/tests/intertree_implementations/test_compare.py test_compare.py-20060724101752-09ysswo1a92uqyoz-2
bzrlib/tests/per_repository/__init__.py __init__.py-20060131092037-9564957a7d4a841b
bzrlib/tests/per_repository/helpers.py helpers.py-20070924032407-m460yl9j5gu5ju85-2
bzrlib/tests/per_repository/test__generate_text_key_index.py test__generate_text_-20071114232121-00h9fd8qg8kjfa5k-1
bzrlib/tests/per_repository/test_add_fallback_repository.py test_add_fallback_re-20080215040003-8w9n4ck9uqdxj18m-1
bzrlib/tests/per_repository/test_break_lock.py test_break_lock.py-20060504111704-ee09a107f9f42e43
bzrlib/tests/per_repository/test_check.py test_check.py-20070824124512-38g4d135gcqxo4zb-1
bzrlib/tests/per_repository/test_check_reconcile.py test_broken.py-20070928125406-62236394w0jpbpd6-2
bzrlib/tests/per_repository/test_commit_builder.py test_commit_builder.py-20060606110838-76e3ra5slucqus81-1
bzrlib/tests/per_repository/test_fetch.py test_fetch.py-20070814052151-5cxha9slx4c93uog-1
bzrlib/tests/per_repository/test_fileid_involved.py test_file_involved.py-20051215205901-728a172d1014daaa
bzrlib/tests/per_repository/test_find_text_key_references.py test_find_text_key_r-20071114033605-v73bakal8x77qlfi-1
bzrlib/tests/per_repository/test_get_parent_map.py test_get_parent_map.-20080421172708-x1z6ot341osr0jq1-1
bzrlib/tests/per_repository/test_has_revisions.py test_has_revisions.p-20080111035443-xaupgdsx5fw1q54b-1
bzrlib/tests/per_repository/test_has_same_location.py test_has_same_locati-20070807074648-2i2ah82fbe83iys7-1
bzrlib/tests/per_repository/test_is_write_locked.py test_is_write_locked-20071012063748-vk062lmu683qgbc3-1
bzrlib/tests/per_repository/test_iter_reverse_revision_history.py test_iter_reverse_re-20070217015036-spu7j5ggch7pbpyd-1
bzrlib/tests/per_repository/test_pack.py test_pack.py-20070712120702-0c7585lh56p894mo-2
bzrlib/tests/per_repository/test_reconcile.py test_reconcile.py-20060223022332-572ef70a3288e369
bzrlib/tests/per_repository/test_repository.py test_repository.py-20060131092128-ad07f494f5c9d26c
bzrlib/tests/per_repository/test_revision.py testrevprops.py-20051013073044-92bc3c68302ce1bf
bzrlib/tests/per_repository/test_statistics.py test_statistics.py-20070203082432-6738e8fl0mm7ikre-1
bzrlib/tests/per_repository/test_write_group.py test_write_group.py-20070716105516-89n34xtogq5frn0m-1
bzrlib/tests/per_repository_reference/__init__.py __init__.py-20080220025549-nnm2s80it1lvcwnc-2
bzrlib/tests/test__dirstate_helpers.py test_dirstate_helper-20070504035751-jsbn00xodv0y1eve-2
bzrlib/tests/test__walkdirs_win32.py test__walkdirs_win32-20080716220454-kweh3tgxez5dvw2l-3
bzrlib/tests/test_annotate.py test_annotate.py-20061213215015-sttc9agsxomls7q0-1
bzrlib/tests/test_bundle.py test.py-20050630184834-092aa401ab9f039c
bzrlib/tests/test_bzrdir.py test_bzrdir.py-20060131065654-deba40eef51cf220
bzrlib/tests/test_diff.py testdiff.py-20050727164403-d1a3496ebb12e339
bzrlib/tests/test_directory_service.py test_directory_servi-20080305221044-vr2mkvlsk8jypa2y-2
bzrlib/tests/test_dirstate.py test_dirstate.py-20060728012006-d6mvoihjb3je9peu-2
bzrlib/tests/test_errors.py test_errors.py-20060210110251-41aba2deddf936a8
bzrlib/tests/test_fetch.py testfetch.py-20050825090644-f73e07e7dfb1765a
bzrlib/tests/test_index.py test_index.py-20070712131115-lolkarso50vjr64s-2
bzrlib/tests/test_info.py test_info.py-20070320150933-m0xxm1g7xi9v6noe-1
bzrlib/tests/test_lockdir.py test_lockdir.py-20060220222025-33d4221569a3d600
bzrlib/tests/test_log.py testlog.py-20050728115707-1a514809d7d49309
bzrlib/tests/test_merge.py testmerge.py-20050905070950-c1b5aa49ff911024
bzrlib/tests/test_missing.py test_missing.py-20051212000028-694fa4f658a81f48
bzrlib/tests/test_options.py testoptions.py-20051014093702-96457cfc86319a8f
bzrlib/tests/test_osutils.py test_osutils.py-20051201224856-e48ee24c12182989
bzrlib/tests/test_pack_repository.py test_pack_repository-20080801043947-eaw0e6h2gu75kwmy-1
bzrlib/tests/test_permissions.py test_permissions.py-20051215004520-ccf475789c80e80c
bzrlib/tests/test_reconcile.py test_reconcile.py-20060225054842-50aa618584a86f26
bzrlib/tests/test_remote.py test_remote.py-20060720103555-yeeg2x51vn0rbtdp-2
bzrlib/tests/test_repository.py test_repository.py-20060131075918-65c555b881612f4d
bzrlib/tests/test_revisiontree.py test_revisiontree.py-20060615095324-aij44ndxbv1h4c9f-1
bzrlib/tests/test_selftest.py test_selftest.py-20051202044319-c110a115d8c0456a
bzrlib/tests/test_setup.py test_setup.py-20051208073730-4a59a6368c4efa04
bzrlib/tests/test_sftp_transport.py testsftp.py-20051027032739-247570325fec7e7e
bzrlib/tests/test_smart.py test_smart.py-20061122024551-ol0l0o0oofsu9b3t-2
bzrlib/tests/test_smart_transport.py test_ssh_transport.py-20060608202016-c25gvf1ob7ypbus6-2
bzrlib/tests/test_status.py test_status.py-20060516190614-fbf6432e4a6e8aa5
bzrlib/tests/test_transform.py test_transaction.py-20060105172520-b3ffb3946550e6c4
bzrlib/tests/test_transport.py testtransport.py-20050718175618-e5cdb99f4555ddce
bzrlib/tests/test_transport_implementations.py test_transport_implementations.py-20051227111451-f97c5c7d5c49fce7
bzrlib/tests/test_upgrade_stacked.py test_upgrade_stacked-20080804072225-jd13yami19nskns5-1
bzrlib/tests/test_whitebox.py whitebox.py-20050530064534-a063aafb4a0a3a04
bzrlib/tests/test_win32utils.py test_win32utils.py-20070713181630-8xsrjymd3e8mgw23-108
bzrlib/tests/tree_implementations/__init__.py __init__.py-20060717075546-420s7b0bj9hzeowi-2
bzrlib/tests/tree_implementations/test_inv.py test_inv.py-20070312023226-0cdvk5uwhutis9vg-1
bzrlib/tests/tree_implementations/test_test_trees.py test_tree_trees.py-20060720091921-3nwi5h21lf06vf5p-1
bzrlib/tests/tree_implementations/test_tree.py test_tree.py-20061215160206-usu7lwcj8aq2n3br-1
bzrlib/tests/tree_implementations/test_walkdirs.py test_walkdirs.py-20060729160421-gmjnkotqgxdh98ce-1
bzrlib/tests/workingtree_implementations/test_parents.py test_set_parents.py-20060807231740-yicmnlci1mj8smu1-1
bzrlib/tests/workingtree_implementations/test_remove.py test_remove.py-20070413183901-rvnp85rtc0q0sclp-1
bzrlib/tests/workingtree_implementations/test_rename_one.py test_rename_one.py-20070226161242-2d8ibdedl700jgio-1
bzrlib/tests/workingtree_implementations/test_workingtree.py test_workingtree.py-20060203003124-817757d3e31444fb
bzrlib/transform.py transform.py-20060105172343-dd99e54394d91687
bzrlib/transport/__init__.py transport.py-20050711165921-4978aa7ce1285ad5
bzrlib/transport/http/__init__.py http_transport.py-20050711212304-506c5fd1059ace96
bzrlib/transport/http/_pycurl.py pycurlhttp.py-20060110060940-4e2a705911af77a6
bzrlib/transport/local.py local_transport.py-20050711165921-9b1f142bfe480c24
bzrlib/transport/remote.py ssh.py-20060608202016-c25gvf1ob7ypbus6-1
bzrlib/transport/sftp.py sftp.py-20051019050329-ab48ce71b7e32dfe
bzrlib/transport/trace.py trace.py-20070828055009-7kt0bbc4t4b92apz-1
bzrlib/tree.py tree.py-20050309040759-9d5f2496be663e77
bzrlib/win32utils.py win32console.py-20051021033308-123c6c929d04973d
bzrlib/workingtree.py workingtree.py-20050511021032-29b6ec0a681e02e3
bzrlib/workingtree_4.py workingtree_4.py-20070208044105-5fgpc5j3ljlh5q6c-1
doc/developers/HACKING.txt HACKING-20050805200004-2a5dc975d870f78c
doc/developers/development-repo.txt developmentrepo.txt-20080102200205-raj42k61dch8pjmj-1
doc/developers/index.txt index.txt-20070508041241-qznziunkg0nffhiw-1
doc/developers/ppa.txt ppa.txt-20080722055539-606u7t2z32t3ae4w-1
doc/en/mini-tutorial/index.txt index.txt-20070813141352-2u64ooqzo0or4hss-2
doc/en/user-guide/http_smart_server.txt fastcgi.txt-20061005091552-rz8pva0olkxv0sd8-3
doc/en/user-guide/undoing_mistakes.txt undoing_mistakes.txt-20071121092300-8fyacngt1w98e5mp-1
doc/es/mini-tutorial/index.txt index.txt-20080504182136-wmoc35u2t6kom8ca-1
profile_imports.py profile_imports.py-20060618020306-k5uw80achysrokj9-1
setup.py setup.py-20050314065409-02f8a0a6e3f9bc70
tools/doc_generate/autodoc_man.py bzrman.py-20050601153041-0ff7f74de456d15e
tools/win32/bzr.iss.cog bzr.iss.cog-20060622100836-b3yup582rt3y0nvm-5
------------------------------------------------------------
revno: 3638.5.4
revision-id: robertc at robertcollins.net-20080828033752-6ry5zf5dxsnhibxg
parent: robertc at robertcollins.net-20080827004239-7d2b1m4bsd2u8ufm
committer: Robert Collins <robertc at robertcollins.net>
branch nick: inventory
timestamp: Thu 2008-08-28 13:37:52 +1000
message:
more review feedback.
modified:
doc/developers/inventory.txt inventory.txt-20080103013957-opkrhxy6lmywmx4i-1
------------------------------------------------------------
revno: 3638.5.3
revision-id: robertc at robertcollins.net-20080827004239-7d2b1m4bsd2u8ufm
parent: robertc at robertcollins.net-20080822044646-zhphuxredh9rctjd
committer: Robert Collins <robertc at robertcollins.net>
branch nick: inventory
timestamp: Wed 2008-08-27 10:42:39 +1000
message:
Review feedback on hash trie inventories, and describe radix tree inventories, plus some details on hash trie implementation.
modified:
doc/developers/inventory.txt inventory.txt-20080103013957-opkrhxy6lmywmx4i-1
------------------------------------------------------------
revno: 3638.5.2
revision-id: robertc at robertcollins.net-20080822044646-zhphuxredh9rctjd
parent: robertc at robertcollins.net-20080819013507-bc7a4529lw8ze9b5
committer: Robert Collins <robertc at robertcollins.net>
branch nick: inventory
timestamp: Fri 2008-08-22 14:46:46 +1000
message:
Describe a hash trie based inventory
modified:
doc/developers/inventory.txt inventory.txt-20080103013957-opkrhxy6lmywmx4i-1
------------------------------------------------------------
revno: 3638.5.1
revision-id: robertc at robertcollins.net-20080819013507-bc7a4529lw8ze9b5
parent: pqm at pqm.ubuntu.com-20080816000954-t0401ff8s3ydnkr6
committer: Robert Collins <robertc at robertcollins.net>
branch nick: inventory
timestamp: Tue 2008-08-19 11:35:07 +1000
message:
Improve inventory design docs with current planning thoughts.
modified:
doc/developers/inventory.txt inventory.txt-20080103013957-opkrhxy6lmywmx4i-1
=== modified file 'doc/developers/inventory.txt'
--- a/doc/developers/inventory.txt 2008-01-03 01:40:16 +0000
+++ b/doc/developers/inventory.txt 2008-09-24 07:33:56 +0000
@@ -8,7 +8,9 @@
========
Inventories provide an abstraction for talking about the shape of a tree.
-Generally only tree object implementors should be concerned about inventories.
+Generally only tree object implementors should be concerned about entire
+inventory objects and their implementation. Other common exceptions are
+full-tree operations such as 'checkout', 'export' and 'import'.
In memory inventories
=====================
@@ -39,9 +41,413 @@
All the xml serialized forms write to and read from a single byte string, whose
hash is then the inventory validator for the commit object.
-journalled
-----------
-
-The in development journalled inventory serializer generates a single byte
-string during serialization, but may require many byte strings to deserialize,
-and these are discovered recursively.
+
+Serialization scaling and future designs
+========================================
+
+Overall efficiency and scaling is constrained by the bottom level structure
+that an inventory is stored as. We have a number of goals we want to achieve:
+
+ 1. Allow commit to write less than the full tree's data in to the repository
+ in the general case.
+ 2. Allow the data that is written to be calculated without examining every
+ versioned path in the tree.
+ 3. Generate the exact same representation for a given inventory regardless of
+ the amount of history available.
+ 4. Allow in memory deltas to be generated directly from the serialised form
+ without upcasting to a full in-memory representation or examining every
+ path in the tree. Ideally the work performed will be proportional to the
+ amount of changes between the trees being compared.
+ 5. Allow fetch to determine the file texts that need to be pulled to ensure
+ that the entire tree can be reconstructed without having to probe every
+ path in the tree.
+ 6. Allow bzr to map paths to file ids without reading the entire serialised
+ form. This is something that is used by commands such as merge PATH and
+ diff -r X PATH.
+ 7. Let bzr map file ids to paths without reading the entire serialised form.
+ This is used by commands that are presenting output to the user such as
+ loggerhead, bzr-search, log FILENAME.
+ 8. We want a strong validator for inventories which is cheap to generate.
+ Specifically we should be able to create the generator for a new commit
+ without processing all the data of the basis commit.
+ 9. Testaments generation is currently size(tree), we would like to create a
+ new testament standard which requires less work so that signed commits
+ are not significantly slower than regular commits.
+
+
+We have current performance and memory bugs in log -v, merge, commit, diff -r,
+loggerhead and status -r which can be addressed by an inventory system
+meeting these goals.
+
+Current situation
+-----------------
+
+The xml based implementation we use today layers the inventory as a bytestring
+which is stored under a single key; the bytestring is then compressed as a
+delta against the bytestring of its left hand parent by the knit code.
+
+Gap analysis:
+
+ 1. Succeeds
+ 2. Fails - generating a new xml representation needs full tree data.
+ 3. Succeeds - the inventory layer accesses the bytestring, which is
+ deterministic
+ 4. Fails - we have to reconstruct both inventories as trees and then delta
+ the resulting in memory objects.
+ 5. Partial success - the revision field in the inventory can be scanned for
+ in both text-delta and full-bytestring form; other revision values than
+ those revisions which are being pulled are by definition absent.
+ 6. Partially succeeds - with appropriate logic a path<->id map can be generated
+ just-in-time, but it is complex and still requires reconstructing the
+ entire byte-string.
+ 7. As for 6.
+ 8. Fails - we have to hash the entire tree in serialised form to generate
+ validators.
+ 9. Fails.
+
+Long term work
+--------------
+
+Some things are likely harder to fix incrementally than others. In particular,
+goal 3 (constant canonical form) is arguably only achieved if we remove all
+derived data such as the last-modified revision from the inventory itself. That
+said, the last-modified appears to be in a higher level than raw serialization.
+So in the medium term we will not alter the contents of inventories, only the
+way that the current contents are mapped to and from disk.
+
+
+Layering
+--------
+
+We desire clear and clean layers. Each layer should be as simple as we can make
+it to aid in debugging and performance tuning. So where we can choose to either
+write a complex layer and something simple on top of it, or two layers with
+neither being as complex - then we should consider the latter choice better in
+the absence of compelling reasons not to.
+
+Some key layers we have today and can look at using or tweaking are:
+
+ * Tree objects - the abstract interface bzrlib code works in
+ * VersionedFiles - the optionally delta compressing key->bytes storage
+ interface.
+ * Inventory - the abstract interface that many tree operations are written in.
+
+These layers are probably sufficient with minor tweaking. We may want to add
+additional modules/implementations of one or more layers, but that doesn't
+really require new layers to be exposed.
+
+Design elements to achieve the goals in a future inventory implementation
+-------------------------------------------------------------------------
+
+ * Split up the logical document into smaller serialised fragements. For
+ instance hash buckets or nodes in a tree of some sort. By serialising in
+ smaller units, we can increase the number of smaller units rather than
+ their size as the tree grows; as long as two similar trees have similar
+ serialised forms, the amount of different content should be quite high.
+
+ * Use fragment identifiers that are independent of revision id, so that
+ serialisation of two related trees generates overlap in the keyspace
+ for fragments without requiring explicit delta logic. Content Hash Keys
+ (e.g. ('sha1:ABCDEF0123456789...',) are useful here because of the ability
+ to assign them without reference to history.)
+
+ * Store the fragments in our existing VersionedFiles store. Adding an index
+ for them. Have the serialised form be uncompressed utf8, so that delta logic
+ in the VersionedFiles layer can be used. We may need to provide some sort
+ of hinting mechanism to get good compression - but the trivially available
+ zlib compression of knits-with-no-deltas is probably a good start.
+
+ * Item_keys_introduced_by is innately a history-using function; we can
+ reproduce the text-key finding logic by doing a tree diff between any tree
+ and an older tree - that will limit the amount of data we need to process
+ to something proportional to the difference and the size of each fragment.
+ When checking many versions we can track which fragments we have examined
+ and only look at new unique ones as each version is examined in turn.
+
+ * Working tree to arbitrary history revision deltas/comparisons can be scaled
+ up by doing a two-step (fixed at two!) delta combining - delta(tree, basis)
+ and then combine that with delta(basis, arbitrary_revision) using the
+ repositories ability to get a delta cheaply.
+
+ * The key primitives we need seem to be:
+ * canonical_form(inventory) -> fragments
+ * delta(inventory, inventory) -> inventory_delta
+ * apply(inventory_delta, canonical_form) -> fragments
+
+ * Having very many small fragments is likely to cause a high latency
+ multiplier unless we are careful.
+
+ * Possible designs to investigate - a hash bucket approach, radix trees,
+ B+ trees, directory trees (with splits inside a directory?).
+
+
+Hash bucket based inventories
+=============================
+
+Overview
+--------
+
+We store two maps - fileid:inventory_entry and path:fileid, in a stable
+hash trie, stored in densly packed fragments. We pack keys into the map
+densely up the tree, with a single canonical form for any given tree. This is
+more stable than simple fixed size buckets, which prevents corner cases where
+the tree size varies right on a bucket size border. (Note that such cases are
+not a fatal flaw - the two forms would both be present in the repository, so
+only a small amount of data would be written at each transition - but a full
+tree reprocess would be needed at each tree operation across the boundary, and
+thats undesirable.)
+
+Goal satisfaction
+-----------------
+
+ 1. Success
+ 2. Success
+ 3. Success
+ 4. Success, though each change will need its parents looked up as well
+ so it will be proportional to the changes + the directories above
+ the changed path.
+ 5. Success - looking at the difference against all parents we can determine
+ new keys without reference to the repository content will be inserted
+ into.
+ 6. This probably needs a path->id map, allowing a 2-step lookup.
+ 7. If we allocate buckets by hashing the id, then this is succeed, though,
+ as per 4 it will need recursive lookups.
+ 8. Success
+ 9. Fail - data beyond that currently included in testaments is included
+ in the strong validator.
+
+Issues
+------
+
+ 1. Tuning the fragment size needs doing.
+ 1. Testing.
+ 1. Writing code.
+ 1. Separate root node, or inline into revision?
+ 1. Cannot do 'ls' efficiently in the current design.
+ 1. Cannot detect invalid deltas easily.
+ 1. What about LCA merge of inventories?
+
+Canonical form
+--------------
+
+There are three fragment types for the canonical form. Each fragment is
+addressed using a Content Hash Key (CHK) - for instance
+"sha1:12345678901234567890".
+
+root_node: (Perhaps this should be inlined into the revision object).
+HASH_INVENTORY_SIGNATURE
+path_map: CHK to root of path to id map
+content_map: CHK to root of id to entry map
+
+map_node: INTERNAL_NODE or LEAF_NODE
+INTERNAL_NODE:
+INTERNAL_NODE_SIGNATURE
+hash_prefix: PREFIX
+prefix_width: INT
+PREFIX CHK TYPE SIZE
+PREFIX CHK TYPE SIZE ...
+
+(Where TYPE is I for internal or L for leaf).
+
+leaf_node:
+LEAF_NODE_SIGNATURE
+hash_prefix: PREFIX
+HASH\x00KEY\x00 VALUE
+
+For path maps, VALUE is::
+ fileid
+
+For content maps, VALUE::
+ fileid basename kind last-changed kind-specific-details
+
+
+The path and content maps are populated simply by serialising every inventory
+entry and inserting them into both the path map and the content map. The maps
+start with just a single leaf node with an empty prefix.
+
+
+Apply
+-----
+
+Given an inventory delta - a list of (old_path, new_path, InventoryEntry)
+items, with a None in new_path indicating a delete operation, and recursive
+deletes not being permitted - all entries to be deleted must be explicitly
+listed, we can transform a current inventory directly. We can't trivially
+detect an invalid delta though.
+
+To perform an application, naively we can just update both maps. For the path
+map we would remove all entries where the paths in the delta do not match, then
+insert those with a new_path again. For the content map we would just remove
+all the fileids in the delta, then insert those with a new_path that is not
+None.
+
+Delta
+-----
+
+To generate a delta between two inventories, we first generate a list of
+altered fileids, and then recursively look up their parents to generate their
+old and new file paths.
+
+To generate the list of altered file ids, we do an entry by entry comparison of
+the full contents of every leaf node that the two inventories do not have in
+common. To do this, we start at the root node, and follow every CHK pointer
+that is only in one tree. We can then bring in all the values from the leaf
+nodes and do a set difference to get the altered ones, which we would then
+parse.
+
+
+Radix tree based inventories
+============================
+
+Overview
+--------
+
+We store two maps - fileid:path and path:inventory_entry. The fileid:path map
+is a hash trie (as file ids have no useful locality of reference). The
+path:inventory_entry map is stored as a regular trie. As for hash tries we
+define a single canonical representation for regular tries similar to that
+defined above for hash tries.
+
+Goal satisfaction
+-----------------
+
+ 1. Success
+ 2. Success
+ 3. Success
+ 4. Success
+ 5. Success - looking at the difference against all parents we can determine
+ new keys without reference to the repository content will be inserted
+ into.
+ 6. Success
+ 7. Success
+ 8. Success
+ 9. Fail - data beyond that currently included in testaments is included
+ in the strong validator.
+
+Issues
+------
+
+ 1. Tuning the fragment size needs doing.
+ 1. Testing.
+ 1. Writing code.
+ 1. Separate root node, or inline into revision?
+ 1. What about LCA merge of inventories?
+
+Canonical form
+--------------
+
+There are five fragment types for the canonical form:
+
+The root node, hash trie internal and leaf nodes as previous.
+
+Then we have two more, the internal and leaf node for the radix tree.
+
+radix_node: INTERNAL_NODE or LEAF_NODE
+
+INTERNAL_NODE:
+INTERNAL_NODE_SIGNATURE
+prefix: PREFIX
+suffix CHK TYPE SIZE
+suffix CHK TYPE SIZE ...
+
+(Where TYPE is I for internal or L for leaf).
+
+LEAF_NODE:
+LEAF_NODE_SIGNATURE
+prefix: PREFIX
+suffix\x00VALUE
+
+For the content map we use the same value as for hashtrie inventories.
+
+
+Node splitting and joining in the radix tree are managed in the same fashion as
+as for the internal nodes of the hashtries.
+
+
+Apply
+-----
+
+Apply is implemented as for hashtries - we just remove and reinsert the
+fileid:paths map entries, and likewise for the path:entry map. We can however
+cheaply detect invalid deltas where a delete fails to include its children.
+
+Delta
+-----
+
+Delta generation is very similar to that with hash tries, except we get the
+path of nodes as part of the lookup process.
+
+
+Hash Trie details
+=================
+
+The canonical form for a hash trie is a tree of internal nodes leading down to
+leaf nodes, with no node exceeding some threshold size, and every node
+containing as much content as it can, but no leaf node containing less than
+its lower size threshold. (In the event that an imbalance in the hash function
+causes a tree where an internal node is needed, but any prefix generates a
+child with less than the lower threshold, the smallest prefix should be taken).
+An internal node holds some number of key prefixes, all with the same bit-width.
+A leaf node holds the actual values. As trees do not spring fully-formed, the
+canonical form is defined iteratively - by taking every item in a tree and
+inserting it into a new tree in order you can determine what canonical form
+would look like. As that is an expensive operation, it should only be done
+rarely.
+
+Updates to a tree that is in canonical form can be done preserving canonical
+form if we can prove that our rules for insertion are order-independent,
+and that our rules for deletion generate the same tree as if we never
+inserted those nodes.
+
+Our hash tries are balanced vertically but not horizontally. That is, one leg
+of a tree can be arbitrarily deeper than adjacent legs. We require that each
+node along a path within the tree be densely packed, with the densest nodes
+near the top of the tree, and the least dense at the bottom. Except where the
+tree cannot support it, no node is smaller than a minimum_size, and none
+larger than maximum_size. The minimum size constraint is only applied when
+there are enough entries under a prefix to meet that minimum. The maximum
+size constraint is always applied except when a node with a single entry
+is larger than the maximum size. Loosely, the maximum size constraint wins
+over the minimum size constraint, and if the minimum size contraint is to
+be ignored, a deeper prefix can be chosen to pack the containing node more
+densely, as long as no additional minimum sizes checks on child nodes are
+violated.
+
+Insertion
+---------
+
+#. Hash the entry, and insert the entry in the leaf node with a matching
+ prefix, creating that node and linking it from the internal node containing
+ that prefix if there is no appropriate leaf node.
+#. Starting at the highest node altered, for all altered nodes, check if it has
+ transitioned across either size boundary - 0 < min_size < max_size. If it
+ has not, proceed to update the CHK pointers.
+#. If it increased above min_size, check the node above to see if it can be
+ more densely packed. To be below the min_size the node's parent must
+ have hit the max size constraint and been forced to split even though this
+ child did not have enough content to support a min_size node - so the prefix
+ chosen in the parent may be shorter than desirable and we may now be able
+ to more densely pack the parent by splitting the child nodes more. So if the
+ parent node can support a deeper prefix without hitting max_size, and the
+ count of under min_size nodes cannot be reduced, the parent should be given
+ a deeper prefix.
+#. If it increased above max_size, shrink the prefix width used to split out
+ new nodes until the node is below max_size (unless the prefix width is
+ already 1 - the minimum).
+ To shrink the prefix of an internal node, create new internal nodes for each
+ new prefix, and populate them with the content of the nodes which were
+ formerly linked. (This will normally bubble down due to keeping densely
+ packed nodes).
+ To shrink the prefix of a leaf node, create an internal node with the same
+ prefix, then choose a width for the internal node such that the contents
+ of the leaf all fit into new leaves obeying the min_size and max_size rules.
+ The largest prefix possible should be chosen, to obey the
+ higher-nodes-are-denser rule. That rule also gives room in leaf nodes for
+ growth without affecting the parent node packing.
+#. Update the CHK pointers - serialise every altered node to generate a CHK,
+ and update the CHK placeholder in the nodes parent; then reserialise the
+ parent. CHK pointer propogation can be done lazily when many updates are
+ expected.
+
+Multiple versions of nodes for the same PREFIX and internal prefix width should
+compress well for the same tree.
More information about the bazaar-commits
mailing list