# (Be in -*- python -*- mode.) # # ==================================================================== # Copyright (c) 2007-2009 CollabNet. All rights reserved. # # This software is licensed as described in the file COPYING, which # you should have received as part of this distribution. The terms # are also available at http://subversion.tigris.org/license-1.html. # If newer versions of this license are posted there, you may use a # newer version instead, at your option. # # This software consists of voluntary contributions made by many # individuals. For exact contribution history, see the revision # history and logs, available at http://cvs2svn.tigris.org/. # ==================================================================== """This module contains classes that implement the --use-internal-co option. The idea is to patch up the revisions' contents incrementally, thus avoiding the huge number of process spawns and the O(n^2) overhead of using 'co' and 'cvs'. InternalRevisionCollector saves the RCS deltas and RCS revision trees to databases. Notably, deltas from the trunk need to be reversed, as CVS stores them so they apply from HEAD backwards. InternalRevisionReader produces the revisions' contents on demand. To generate the text for a typical revision, we need the revision's delta text plus the fulltext of the previous revision. Therefore, we maintain a checkout database containing a copy of the fulltext of any revision for which subsequent revisions still need to be retrieved. It is crucial to remove text from this database as soon as it is no longer needed, to prevent it from growing enormous. There are two reasons that the text from a revision can be needed: (1) because the revision itself still needs to be output to a dumpfile; (2) because another revision needs it as the base of its delta. We maintain a reference count for each revision, which includes *both* possibilities. The first time a revision's text is needed, it is generated by applying the revision's deltatext to the previous revision's fulltext, and the resulting fulltext is stored in the checkout database. Each time a revision's fulltext is retrieved, its reference count is decremented. When the reference count goes to zero, then the fulltext is deleted from the checkout database. The administrative data for managing this consists of one TextRecord entry for each revision. Each TextRecord has an id, which is the same id as used for the corresponding CVSRevision instance. It also maintains a count of the times it is expected to be retrieved. TextRecords come in several varieties: FullTextRecord -- Used for revisions whose fulltext is derived directly from the RCS file by the InternalRevisionCollector (i.e., typically revision 1.1 of each file). DeltaTextRecord -- Used for revisions that are defined via a delta relative to some other TextRecord. These records record the id of the TextRecord that holds the base text against which the delta is defined. When the text for a DeltaTextRecord is retrieved, the DeltaTextRecord instance is deleted and a CheckedOutTextRecord instance is created to take its place. CheckedOutTextRecord -- Used during OutputPass for a revision that started out as a DeltaTextRecord, but has already been retrieved (and therefore its fulltext is stored in the checkout database). While a file is being processed during FilterSymbolsPass, the fulltext and deltas are stored to the delta database, and TextRecord instances are created to keep track of things. The reference counts are all initialized: each record referred to by a delta has its refcount incremented, and each record that corresponds to a non-delete CVSRevision is incremented. After that, any records with refcount==0 are removed. When one record is removed, that can cause another record's reference count to go to zero and be removed too, recursively. When a TextRecord is deleted at this stage, its deltatext is also deleted from the delta database.""" from cvs2svn_lib import config from cvs2svn_lib.common import DB_OPEN_NEW from cvs2svn_lib.common import DB_OPEN_READ from cvs2svn_lib.common import warning_prefix from cvs2svn_lib.common import FatalError from cvs2svn_lib.common import InternalError from cvs2svn_lib.common import canonicalize_eol from cvs2svn_lib.common import is_trunk_revision from cvs2svn_lib.context import Ctx from cvs2svn_lib.log import logger from cvs2svn_lib.artifact_manager import artifact_manager from cvs2svn_lib.cvs_item import CVSRevisionModification from cvs2svn_lib.indexed_database import IndexedDatabase from cvs2svn_lib.rcs_stream import RCSStream from cvs2svn_lib.rcs_stream import MalformedDeltaException from cvs2svn_lib.keyword_expander import expand_keywords from cvs2svn_lib.keyword_expander import collapse_keywords from cvs2svn_lib.revision_manager import RevisionCollector from cvs2svn_lib.revision_manager import RevisionReader from cvs2svn_lib.serializer import MarshalSerializer from cvs2svn_lib.serializer import CompressingSerializer from cvs2svn_lib.serializer import PrimedPickleSerializer from cvs2svn_lib.apple_single_filter import get_maybe_apple_single from cvs2svn_lib.rcsparser import Sink from cvs2svn_lib.rcsparser import parse class TextRecord(object): """Bookkeeping data for the text of a single CVSRevision.""" __slots__ = ['id', 'refcount'] def __init__(self, id): # The cvs_rev_id of the revision whose text this is. self.id = id # The number of times that the text of this revision will be # retrieved. self.refcount = 0 def __getstate__(self): return (self.id, self.refcount,) def __setstate__(self, state): (self.id, self.refcount,) = state def increment_dependency_refcounts(self, text_record_db): """Increment the refcounts of any records that this one depends on.""" pass def decrement_refcount(self, text_record_db): """Decrement the number of times our text still has to be checked out. If the reference count goes to zero, call discard().""" self.refcount -= 1 if self.refcount == 0: text_record_db.discard(self.id) def checkout(self, text_record_db): """Workhorse of the checkout process. Return the text for this revision, decrement our reference count, and update the databases depending on whether there will be future checkouts.""" raise NotImplementedError() def free(self, text_record_db): """This instance will never again be checked out; free it. Also free any associated resources and decrement the refcounts of any other TextRecords that this one depends on.""" raise NotImplementedError() class FullTextRecord(TextRecord): """A record whose revision's fulltext is stored in the delta_db. These records are used for revisions whose fulltext was determined by the InternalRevisionCollector during FilterSymbolsPass. The fulltext for such a revision is is stored in the delta_db as a single string.""" __slots__ = [] def __getstate__(self): return (self.id, self.refcount,) def __setstate__(self, state): (self.id, self.refcount,) = state def checkout(self, text_record_db): text = text_record_db.delta_db[self.id] self.decrement_refcount(text_record_db) return text def free(self, text_record_db): del text_record_db.delta_db[self.id] def __str__(self): return 'FullTextRecord(%x, %d)' % (self.id, self.refcount,) class DeltaTextRecord(TextRecord): """A record whose revision's delta is stored as an RCS delta. The text of this revision must be derived by applying an RCS delta to the text of the predecessor revision. The RCS delta is stored in the delta_db.""" __slots__ = ['pred_id'] def __init__(self, id, pred_id): TextRecord.__init__(self, id) # The cvs_rev_id of the revision relative to which this delta is # defined. self.pred_id = pred_id def __getstate__(self): return (self.id, self.refcount, self.pred_id,) def __setstate__(self, state): (self.id, self.refcount, self.pred_id,) = state def increment_dependency_refcounts(self, text_record_db): text_record_db[self.pred_id].refcount += 1 def checkout(self, text_record_db): base_text = text_record_db[self.pred_id].checkout(text_record_db) rcs_stream = RCSStream(base_text) delta_text = text_record_db.delta_db[self.id] rcs_stream.apply_diff(delta_text) text = rcs_stream.get_text() del rcs_stream self.refcount -= 1 if self.refcount == 0: # This text will never be needed again; just delete ourselves # without ever having stored the fulltext to the checkout # database: del text_record_db[self.id] else: # Store a new CheckedOutTextRecord in place of ourselves: text_record_db.checkout_db['%x' % self.id] = text new_text_record = CheckedOutTextRecord(self.id) new_text_record.refcount = self.refcount text_record_db.replace(new_text_record) return text def free(self, text_record_db): del text_record_db.delta_db[self.id] text_record_db[self.pred_id].decrement_refcount(text_record_db) def __str__(self): return 'DeltaTextRecord(%x -> %x, %d)' % ( self.pred_id, self.id, self.refcount, ) class CheckedOutTextRecord(TextRecord): """A record whose revision's fulltext is stored in the text_record_db. These records are used for revisions whose fulltext has been computed already during OutputPass. The fulltext for such a revision is stored in the text_record_db as a single string.""" __slots__ = [] def __getstate__(self): return (self.id, self.refcount,) def __setstate__(self, state): (self.id, self.refcount,) = state def checkout(self, text_record_db): text = text_record_db.checkout_db['%x' % self.id] self.decrement_refcount(text_record_db) return text def free(self, text_record_db): del text_record_db.checkout_db['%x' % self.id] def __str__(self): return 'CheckedOutTextRecord(%x, %d)' % (self.id, self.refcount,) class NullDatabase(object): """A do-nothing database that can be used with TextRecordDatabase. Use this when you don't actually want to allow anything to be deleted.""" def __delitem__(self, id): pass class TextRecordDatabase: """Holds the TextRecord instances that are currently live. During FilterSymbolsPass, files are processed one by one and a new TextRecordDatabase instance is used for each file. During OutputPass, a single TextRecordDatabase instance is used for the duration of OutputPass; individual records are added and removed when they are active.""" def __init__(self, delta_db, checkout_db): # A map { cvs_rev_id -> TextRecord }. self.text_records = {} # A database-like object using cvs_rev_ids as keys and containing # fulltext/deltatext strings as values. Its __getitem__() method # is used to retrieve deltas when they are needed, and its # __delitem__() method is used to delete deltas when they can be # freed. The modifiability of the delta database varies from pass # to pass, so the object stored here varies as well: # # FilterSymbolsPass: a NullDatabase. The delta database cannot be # modified during this pass, and we have no need to retrieve # deltas, so we just use a dummy object here. # # OutputPass: a disabled IndexedDatabase. During this pass we # need to retrieve deltas, but we are not allowed to modify # the delta database. So we use an IndexedDatabase whose # __del__() method has been disabled to do nothing. self.delta_db = delta_db # A database-like object using cvs_rev_ids as keys and containing # fulltext strings as values. This database is only set during # OutputPass. self.checkout_db = checkout_db # If this is set to a list, then the list holds the ids of # text_records that have to be deleted; when discard() is called, # it adds the requested id to the list but does not delete it. If # this member is set to None, then text_records are deleted # immediately when discard() is called. self.deferred_deletes = None def __getstate__(self): return (self.text_records.values(),) def __setstate__(self, state): (text_records,) = state self.text_records = {} for text_record in text_records: self.add(text_record) self.delta_db = NullDatabase() self.checkout_db = NullDatabase() self.deferred_deletes = None def add(self, text_record): """Add TEXT_RECORD to our database. There must not already be a record with the same id.""" assert not self.text_records.has_key(text_record.id) self.text_records[text_record.id] = text_record def __getitem__(self, id): return self.text_records[id] def __delitem__(self, id): """Free the record with the specified ID.""" del self.text_records[id] def replace(self, text_record): """Store TEXT_RECORD in place of the existing record with the same id. Do not do anything with the old record.""" assert self.text_records.has_key(text_record.id) self.text_records[text_record.id] = text_record def discard(self, *ids): """The text records with IDS are no longer needed; discard them. This involves calling their free() methods and also removing them from SELF. If SELF.deferred_deletes is not None, then the ids to be deleted are added to the list instead of deleted immediately. This mechanism is to prevent a stack overflow from the avalanche of deletes that can result from deleting a long chain of revisions.""" if self.deferred_deletes is None: # This is an outer-level delete. self.deferred_deletes = list(ids) while self.deferred_deletes: id = self.deferred_deletes.pop() text_record = self[id] if text_record.refcount != 0: raise InternalError( 'TextRecordDatabase.discard(%s) called with refcount = %d' % (text_record, text_record.refcount,) ) # This call might cause other text_record ids to be added to # self.deferred_deletes: text_record.free(self) del self[id] self.deferred_deletes = None else: self.deferred_deletes.extend(ids) def itervalues(self): return self.text_records.itervalues() def recompute_refcounts(self, cvs_file_items): """Recompute the refcounts of the contained TextRecords. Use CVS_FILE_ITEMS to determine which records will be needed by cvs2svn.""" # First clear all of the refcounts: for text_record in self.itervalues(): text_record.refcount = 0 # Now increment the reference count of records that are needed as # the source of another record's deltas: for text_record in self.itervalues(): text_record.increment_dependency_refcounts(self.text_records) # Now increment the reference count of records that will be needed # by cvs2svn: for lod_items in cvs_file_items.iter_lods(): for cvs_rev in lod_items.cvs_revisions: if isinstance(cvs_rev, CVSRevisionModification): self[cvs_rev.id].refcount += 1 def free_unused(self): """Free any TextRecords whose reference counts are zero.""" # The deletion of some of these text records might cause others to # be unused, in which case they will be deleted automatically. # But since the initially-unused records are not referred to by # any others, we don't have to be afraid that they will be deleted # before we get to them. But it *is* crucial that we create the # whole unused list before starting the loop. unused = [ text_record.id for text_record in self.itervalues() if text_record.refcount == 0 ] self.discard(*unused) def log_leftovers(self): """If any TextRecords still exist, log them.""" if self.text_records: logger.warn( "%s: internal problem: leftover revisions in the checkout cache:" % warning_prefix) for text_record in self.itervalues(): logger.warn(' %s' % (text_record,)) def __repr__(self): """Debugging output of the current contents of the TextRecordDatabase.""" retval = ['TextRecordDatabase:'] for text_record in self.itervalues(): retval.append(' %s' % (text_record,)) return '\n'.join(retval) class _Sink(Sink): def __init__(self, revision_collector, cvs_file_items): self.revision_collector = revision_collector self.cvs_file_items = cvs_file_items # A map {rev : base_rev} indicating that the text for rev is # stored in CVS as a delta relative to base_rev. self.base_revisions = {} # The revision that is stored with its fulltext in CVS (usually # the oldest revision on trunk): self.head_revision = None # The first logical revision on trunk (usually '1.1'): self.revision_1_1 = None # Keep track of the revisions whose revision info has been seen so # far (to avoid repeated revision info blocks): self.revisions_seen = set() def set_head_revision(self, revision): self.head_revision = revision def define_revision( self, revision, timestamp, author, state, branches, next ): if next: self.base_revisions[next] = revision else: if is_trunk_revision(revision): self.revision_1_1 = revision for branch in branches: self.base_revisions[branch] = revision def set_revision_info(self, revision, log, text): if revision in self.revisions_seen: # One common form of CVS repository corruption is that the # Deltatext block for revision 1.1 appears twice. CollectData # has already warned about this problem; here we can just ignore # it. return else: self.revisions_seen.add(revision) cvs_rev_id = self.cvs_file_items.original_ids[revision] if is_trunk_revision(revision): # On trunk, revisions are encountered in reverse order (1. # ... 1.1) and deltas are inverted. The first text that we see # is the fulltext for the HEAD revision. After that, the text # corresponding to revision 1.N is the delta (1. -> # 1.)). We have to invert the deltas here so that we can # read the revisions out in dependency order; that is, for # revision 1.1 we want the fulltext, and for revision 1. we # want the delta (1. -> 1.). This means that we can't # compute the delta for a revision until we see its logical # parent. When we finally see revision 1.1 (which is recognized # because it doesn't have a parent), we can record the diff (1.1 # -> 1.2) for revision 1.2, and also the fulltext for 1.1. if revision == self.head_revision: # This is HEAD, as fulltext. Initialize the RCSStream so # that we can compute deltas backwards in time. self._rcs_stream = RCSStream(text) self._rcs_stream_revision = revision else: # Any other trunk revision is a backward delta. Apply the # delta to the RCSStream to mutate it to the contents of this # revision, and also to get the reverse delta, which we store # as the forward delta of our child revision. try: text = self._rcs_stream.invert_diff(text) except MalformedDeltaException, e: logger.error( 'Malformed RCS delta in %s, revision %s: %s' % (self.cvs_file_items.cvs_file.rcs_path, revision, e) ) raise RuntimeError() text_record = DeltaTextRecord( self.cvs_file_items.original_ids[self._rcs_stream_revision], cvs_rev_id ) self.revision_collector._writeout(text_record, text) self._rcs_stream_revision = revision if revision == self.revision_1_1: # This is revision 1.1. Write its fulltext: text_record = FullTextRecord(cvs_rev_id) self.revision_collector._writeout( text_record, self._rcs_stream.get_text() ) # There will be no more trunk revisions delivered, so free the # RCSStream. del self._rcs_stream del self._rcs_stream_revision else: # On branches, revisions are encountered in logical order # (.1 ... .) and the text corresponding to # revision . is the forward delta (. -> # .). That's what we need, so just store it. # FIXME: It would be nice to avoid writing out branch deltas # when --trunk-only. (They will be deleted when finish_file() # is called, but if the delta db is in an IndexedDatabase the # deletions won't actually recover any disk space.) text_record = DeltaTextRecord( cvs_rev_id, self.cvs_file_items.original_ids[self.base_revisions[revision]] ) self.revision_collector._writeout(text_record, text) return None class InternalRevisionCollector(RevisionCollector): """The RevisionCollector used by InternalRevisionReader.""" def __init__(self, compress): RevisionCollector.__init__(self) self._compress = compress def register_artifacts(self, which_pass): artifact_manager.register_temp_file( config.RCS_DELTAS_INDEX_TABLE, which_pass ) artifact_manager.register_temp_file(config.RCS_DELTAS_STORE, which_pass) artifact_manager.register_temp_file( config.RCS_TREES_INDEX_TABLE, which_pass ) artifact_manager.register_temp_file(config.RCS_TREES_STORE, which_pass) def start(self): serializer = MarshalSerializer() if self._compress: serializer = CompressingSerializer(serializer) self._delta_db = IndexedDatabase( artifact_manager.get_temp_file(config.RCS_DELTAS_STORE), artifact_manager.get_temp_file(config.RCS_DELTAS_INDEX_TABLE), DB_OPEN_NEW, serializer, ) primer = (FullTextRecord, DeltaTextRecord) self._rcs_trees = IndexedDatabase( artifact_manager.get_temp_file(config.RCS_TREES_STORE), artifact_manager.get_temp_file(config.RCS_TREES_INDEX_TABLE), DB_OPEN_NEW, PrimedPickleSerializer(primer), ) def _writeout(self, text_record, text): self.text_record_db.add(text_record) self._delta_db[text_record.id] = text def process_file(self, cvs_file_items): """Read revision information for the file described by CVS_FILE_ITEMS. Compute the text record refcounts, discard any records that are unneeded, and store the text records for the file to the _rcs_trees database.""" # A map from cvs_rev_id to TextRecord instance: self.text_record_db = TextRecordDatabase(self._delta_db, NullDatabase()) parse( open(cvs_file_items.cvs_file.rcs_path, 'rb'), _Sink(self, cvs_file_items), ) self.text_record_db.recompute_refcounts(cvs_file_items) self.text_record_db.free_unused() self._rcs_trees[cvs_file_items.cvs_file.id] = self.text_record_db del self.text_record_db def finish(self): self._delta_db.close() self._rcs_trees.close() class InternalRevisionReader(RevisionReader): """A RevisionReader that reads the contents from an own delta store.""" def __init__(self, compress): # Only import Database if an InternalRevisionReader is really # instantiated, because the import fails if a decent dbm is not # installed. from cvs2svn_lib.database import Database self._Database = Database self._compress = compress def register_artifacts(self, which_pass): artifact_manager.register_temp_file(config.CVS_CHECKOUT_DB, which_pass) artifact_manager.register_temp_file_needed( config.RCS_DELTAS_STORE, which_pass ) artifact_manager.register_temp_file_needed( config.RCS_DELTAS_INDEX_TABLE, which_pass ) artifact_manager.register_temp_file_needed( config.RCS_TREES_STORE, which_pass ) artifact_manager.register_temp_file_needed( config.RCS_TREES_INDEX_TABLE, which_pass ) def start(self): self._delta_db = IndexedDatabase( artifact_manager.get_temp_file(config.RCS_DELTAS_STORE), artifact_manager.get_temp_file(config.RCS_DELTAS_INDEX_TABLE), DB_OPEN_READ, ) self._delta_db.__delitem__ = lambda id: None self._tree_db = IndexedDatabase( artifact_manager.get_temp_file(config.RCS_TREES_STORE), artifact_manager.get_temp_file(config.RCS_TREES_INDEX_TABLE), DB_OPEN_READ, ) serializer = MarshalSerializer() if self._compress: serializer = CompressingSerializer(serializer) self._co_db = self._Database( artifact_manager.get_temp_file(config.CVS_CHECKOUT_DB), DB_OPEN_NEW, serializer, ) # The set of CVSFile instances whose TextRecords have already been # read: self._loaded_files = set() # A map { CVSFILE : _FileTree } for files that currently have live # revisions: self._text_record_db = TextRecordDatabase(self._delta_db, self._co_db) def _get_text_record(self, cvs_rev): """Return the TextRecord instance for CVS_REV. If the TextRecords for CVS_REV.cvs_file haven't been loaded yet, do so now.""" if cvs_rev.cvs_file not in self._loaded_files: for text_record in self._tree_db[cvs_rev.cvs_file.id].itervalues(): self._text_record_db.add(text_record) self._loaded_files.add(cvs_rev.cvs_file) return self._text_record_db[cvs_rev.id] def get_content(self, cvs_rev): """Check out the text for revision C_REV from the repository. Return the text. If CVS_REV has a property _keyword_handling, use it to determine how to handle RCS keywords in the output: 'collapsed' -- collapse keywords 'expanded' -- expand keywords 'untouched' -- output keywords in the form they are found in the RCS file Note that $Log$ never actually generates a log (which makes test 'requires_cvs()' fail). Revisions may be requested in any order, but if they are not requested in dependency order the checkout database will become very large. Revisions may be skipped. Each revision may be requested only once.""" try: text = self._get_text_record(cvs_rev).checkout(self._text_record_db) except MalformedDeltaException, (msg): raise FatalError( 'Malformed RCS delta in %s, revision %s: %s' % (cvs_rev.cvs_file.rcs_path, cvs_rev.rev, msg) ) keyword_handling = cvs_rev.get_property('_keyword_handling') if keyword_handling == 'untouched': # Leave keywords in the form that they were checked in. pass elif keyword_handling == 'collapsed': text = collapse_keywords(text) elif keyword_handling == 'expanded': text = expand_keywords(text, cvs_rev) else: raise FatalError( 'Undefined _keyword_handling property (%r) for %s' % (keyword_handling, cvs_rev,) ) if Ctx().decode_apple_single: # Insert a filter to decode any files that are in AppleSingle # format: text = get_maybe_apple_single(text) eol_fix = cvs_rev.get_property('_eol_fix') if eol_fix: text = canonicalize_eol(text, eol_fix) return text def finish(self): self._text_record_db.log_leftovers() del self._text_record_db self._delta_db.close() self._tree_db.close() self._co_db.close()