← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to doc/developers/inventory.txt

  • Committer: John Arbash Meinel
  • Date: 2009-07-29 21:35:05 UTC
  • mfrom: (4576 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4577.
  • Revision ID: john@arbash-meinel.com-20090729213505-tkqsvy1zfpocu75w
Merge bzr.dev 4576 in prep for NEWS

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
 - has an entry that is in an impossible state (e.g. a directory with a text
 
549
   size)
 
550
 
 
551
Forms of inventory inconsistency deltas can carry/cause:
 
552
 - An entry newly introduced to a path without also removing or relocating any
 
553
   existing entry at that path. (Duplicate paths)
 
554
 - An entry whose parent id isn't present in the tree. (Missing parent).
 
555
 - Having oldpath or newpath not be actual original path or resulting path.
 
556
   (Wrong path)
 
557
 - An entry whose parent is not a directory. (Under non-directory).
 
558
 - An entry that is internally inconsistent.
 
559
 - An entry that is already present in the tree (Duplicate id)
 
560
 
 
561
Known causes of inconsistency:
 
562
 - A 'new' entry which the inventory already has - when this is a directory
 
563
   even arbitrary file ids under the 'new' entry are more likely to collide on
 
564
   paths.
 
565
 - Removing a directory without recursively removing its children - causes
 
566
   Missing parent.
 
567
 - Recording a change to an entry without including all changed entries found
 
568
   following its parents up to and includin the root - can cause duplicate
 
569
   paths, missing parents, wrong path, under non-directory.
 
570
 
 
571
Avoiding inconsistent deltas
 
572
----------------------------
 
573
 
 
574
The simplest thing is to never create partial deltas, as it is trivial to
 
575
be consistent when all data is examined every time. However users sometimes
 
576
want to specify a subset of the changes in their tree when they do an operation
 
577
which needs to create a delta - such as commit.
 
578
 
 
579
We have a choice about handling user requests that can generate inconsistent
 
580
deltas. We can alter or interpret the request in such a way that the delta will
 
581
be consistent, but perhaps larger than the user had intended. Or we can
 
582
identify problematic situations and abort, specifying to the user why we have
 
583
aborted and likely things they can do to make their request generate a
 
584
consistent delta.
 
585
 
 
586
Currently we attempt to expand/interpret the request so that the user is not
 
587
required to understand all the internal constraints of the system: if they
 
588
request 'foo/bar' we automatically include foo. This works to an extent but on
 
589
review we are creating inconsistent deltas by the way we do this. We need to
 
590
avoid all the known causes of inconsistency in our delta creation logic.