/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to doc/developers/inventory.txt

  • Committer: Robert Collins
  • Date: 2009-07-02 07:22:27 UTC
  • mto: This revision was merged to the branch mainline in revision 4505.
  • Revision ID: robertc@robertcollins.net-20090702072227-a2yzortdrjcnls5c
Add documentation describing how and why we use inventory deltas, and what can go wrong with them.

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/developers/inventory.txt
498
498
delta, the only other valid fields are OLDPATH and 'file-id'. PARENT_ID is ''
499
499
when a delete has been recorded or when recording a new root entry.
500
500
 
 
501
 
 
502
Delta consistency
 
503
=================
 
504
 
 
505
Inventory deltas and more broadly changes between trees are a significant part
 
506
of bzr's core operations: they are key components in status, diff, commit,
 
507
and merge (although merge uses tree transform, deltas contain the changes that
 
508
are applied to the transform). Our ability to perform a given operation depends
 
509
on us creating consistent deltas between trees. Inconsistent deltas lead to
 
510
errors and bugs, or even just unexpected conflicts.
 
511
 
 
512
An inventory delta is a transform to change an inventory A into another
 
513
inventory B (in patch terms its a perfect patch). Sometimes, for instance in a
 
514
regular commit, inventory B is known at the time we create the delta. Other
 
515
times, B is not known because the user is requesting that some parts of the
 
516
second inventory they have are masked out from consideration. When this happens
 
517
we create a delta that when applied to A creates a B we haven't seen in total
 
518
before. In this situation we need to ensure that B will be internally
 
519
consistent. Deltas are unidirectional, a delta(A, B) creates B from A, but
 
520
cannot be used to create A from B.
 
521
 
 
522
Deltas are expressed as a list of (oldpath, newpath, fileid, entry) tuples. The
 
523
fileid, entry elements are normative; the old and new paths are strong hints
 
524
but not currently guaranteed to be accurate. (This is a shame and something we
 
525
should tighten up). Deltas are required to list all removals explicitly -
 
526
removing the parent of an entry doesn't remove the entry.
 
527
 
 
528
Applying a delta to an inventory consists of:
 
529
 - removing all fileids for which entry is None
 
530
 - adding or replacing all other fileids
 
531
 - detecting consistency errors
 
532
 
 
533
An interesting aspect of delta inconsistencies is when we notice them:
 
534
 - Silent errors which our application logic misses
 
535
 - Visible errors we catch during application, so bad data isn't stored in
 
536
   the system.
 
537
 
 
538
The minimum safe level for our application logic would be to catch all errors
 
539
during application. Making generation never generate inconsistent deltas is
 
540
a seperate but necessary condition for robust code.
 
541
 
 
542
An inconsistent delta is one which:
 
543
 - after application to an inventory the inventory is an impossible state.
 
544
 - has the same fileid, or oldpath(not-None), or newpath(not-None) multiple
 
545
   times.
 
546
 - has a fileid field different to the entry.fileid in the same item in the
 
547
   delta.
 
548
 
 
549
Forms of inventory inconsistency deltas can carry/cause:
 
550
 - An entry newly introduced to a path without also removing or relocating any
 
551
   existing entry at that path. (Duplicate paths)
 
552
 - An entry whose parent id isn't present in the tree. (Missing parent).
 
553
 - Having oldpath or newpath not be actual original path or resulting path.
 
554
   (Wrong path)
 
555
 - An entry whose parent is not a directory. (Under non-directory).
 
556
 - An entry that is internally inconsistent.
 
557
 
 
558
Known causes of inconsistency:
 
559
 - A 'new' entry which the inventory already has - when this is a directory
 
560
   even arbitrary file ids under the 'new' entry are more likely to collide on
 
561
   paths.
 
562
 - Removing a directory without recursively removing its children - causes
 
563
   Missing parent.
 
564
 - Recording a change to an entry without including all changed entries found
 
565
   following its parents up to and includin the root - can cause duplicate
 
566
   paths, missing parents, wrong path, under non-directory.
 
567
 
 
568
Avoiding inconsistent deltas
 
569
----------------------------
 
570
 
 
571
The simplest thing is to never create partial deltas, as it is trivial to
 
572
be consistent when all data is examined every time. However users sometimes
 
573
want to specify a subset of the changes in their tree when they do an operation
 
574
which needs to create a delta - such as commit.
 
575
 
 
576
We have a choice about handling user requests that can generate inconsistent
 
577
deltas. We can alter or interpret the request in such a way that the delta will
 
578
be consistent, but perhaps larger than the user had intended. Or we can
 
579
identify problematic situations and abort, specifying to the user why we have
 
580
aborted and likely things they can do to make their request generate a
 
581
consistent delta.
 
582
 
 
583
Currently we attempt to expand/interpret the request so that the user is not
 
584
required to understand all the internal constraints of the system: if they
 
585
request 'foo/bar' we automatically include foo. This works to an extent but on
 
586
review we are creating inconsistent deltas by the way we do this. We need to
 
587
avoid all the known causes of inconsistency in our delta creation logic.