tikhomirov@596: /*
tikhomirov@596:  * Copyright (c) 2013 TMate Software Ltd
tikhomirov@596:  *  
tikhomirov@596:  * This program is free software; you can redistribute it and/or modify
tikhomirov@596:  * it under the terms of the GNU General Public License as published by
tikhomirov@596:  * the Free Software Foundation; version 2 of the License.
tikhomirov@596:  *
tikhomirov@596:  * This program is distributed in the hope that it will be useful,
tikhomirov@596:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@596:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@596:  * GNU General Public License for more details.
tikhomirov@596:  *
tikhomirov@596:  * For information on how to redistribute this software under
tikhomirov@596:  * the terms of a license other than GNU General Public License
tikhomirov@596:  * contact TMate Software at support@hg4j.com
tikhomirov@596:  */
tikhomirov@596: package org.tmatesoft.hg.internal;
tikhomirov@596: 
tikhomirov@596: import static org.tmatesoft.hg.core.HgIterateDirection.OldToNew;
tikhomirov@596: import static org.tmatesoft.hg.repo.HgRepository.BAD_REVISION;
tikhomirov@596: import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION;
tikhomirov@596: 
tikhomirov@596: import java.util.Arrays;
tikhomirov@596: import java.util.BitSet;
tikhomirov@596: import java.util.LinkedList;
tikhomirov@596: 
tikhomirov@596: import org.tmatesoft.hg.core.HgIterateDirection;
tikhomirov@596: import org.tmatesoft.hg.repo.HgDataFile;
tikhomirov@596: import org.tmatesoft.hg.repo.HgRepository;
tikhomirov@628: import org.tmatesoft.hg.repo.HgRuntimeException;
tikhomirov@596: 
tikhomirov@596: /**
tikhomirov@596:  * Piece of file history, identified by path, limited to file revisions from range [chop..init] of changesets, 
tikhomirov@596:  * can be linked to another piece.
tikhomirov@596:  * 
tikhomirov@596:  * @author Artem Tikhomirov
tikhomirov@596:  * @author TMate Software Ltd.
tikhomirov@596:  */
tikhomirov@596: public final class FileRevisionHistoryChunk {
tikhomirov@596: 	private final HgDataFile df;
tikhomirov@596: 	// change ancestry, sequence of file revisions
tikhomirov@596: 	private IntVector fileRevsToVisit;
tikhomirov@691: 	// parent pairs of complete file history, index offset by fileRevFrom
tikhomirov@596: 	private IntVector fileParentRevs;
tikhomirov@691: 	// map file revision to changelog revision (sparse array, only file revisions to visit are set), index offset by fileRevFrom
tikhomirov@596: 	private int[] file2changelog;
tikhomirov@596: 	private int originChangelogRev = BAD_REVISION, originFileRev = BAD_REVISION;
tikhomirov@691: 	private final int csetFrom, csetTo; 
tikhomirov@691: 	private final int fileRevFrom, fileRevTo;
tikhomirov@596: 	
tikhomirov@596: 
tikhomirov@691: 	public FileRevisionHistoryChunk(HgDataFile file, int csetStart, int csetEnd, int fileStart, int fileEnd) {
tikhomirov@691: 		assert fileEnd >= fileStart;
tikhomirov@596: 		df = file;
tikhomirov@691: 		csetFrom = csetStart;
tikhomirov@691: 		csetTo = csetEnd;
tikhomirov@691: 		fileRevFrom = fileStart;
tikhomirov@691: 		fileRevTo = fileEnd;
tikhomirov@596: 	}
tikhomirov@596: 	
tikhomirov@596: 	/**
tikhomirov@596: 	 * @return file at this specific chunk of history (i.e. its path may be different from the paths of other chunks)
tikhomirov@596: 	 */
tikhomirov@596: 	public HgDataFile getFile() {
tikhomirov@596: 		return df;
tikhomirov@596: 	}
tikhomirov@596: 	
tikhomirov@596: 	/**
tikhomirov@596: 	 * @return changeset this file history chunk was chopped at, or {@link HgRepository#NO_REVISION} if none specified
tikhomirov@596: 	 */
tikhomirov@596: 	public int getStartChangeset() {
tikhomirov@691: 		return csetFrom;
tikhomirov@596: 	}
tikhomirov@596: 	
tikhomirov@596: 	/**
tikhomirov@596: 	 * @return changeset this file history chunk ends at
tikhomirov@596: 	 */
tikhomirov@596: 	public int getEndChangeset() {
tikhomirov@691: 		return csetTo;
tikhomirov@596: 	}
tikhomirov@596: 	
tikhomirov@691: 	public void init() throws HgRuntimeException {
tikhomirov@596: 		int[] fileRevParents = new int[2];
tikhomirov@691: 		final int totalFileRevs = fileRevTo - fileRevFrom + 1;
tikhomirov@691: 		fileParentRevs = new IntVector(totalFileRevs * 2, 0);
tikhomirov@691: 		// pretend parents of fileRevStart are not set, regardless of actual state as we are not going to visit them anyway
tikhomirov@691: 		fileParentRevs.add(NO_REVISION, NO_REVISION); 
tikhomirov@691: 		// XXX df.indexWalk(fileRevStart, fileRevEnd, ) might be more effective
tikhomirov@691: 		for (int i = fileRevFrom+1; i <= fileRevTo; i++) {
tikhomirov@596: 			df.parents(i, fileRevParents, null, null);
tikhomirov@596: 			fileParentRevs.add(fileRevParents[0], fileRevParents[1]);
tikhomirov@596: 		}
tikhomirov@596: 		// fileRevsToVisit keep file change ancestry from new to old
tikhomirov@691: 		fileRevsToVisit = new IntVector(totalFileRevs, 0);
tikhomirov@596: 		// keep map of file revision to changelog revision
tikhomirov@691: 		file2changelog = new int[totalFileRevs];
tikhomirov@596: 		// only elements worth visit would get mapped, so there would be unfilled areas in the file2changelog,
tikhomirov@596: 		// prevent from error (make it explicit) by bad value
tikhomirov@596: 		Arrays.fill(file2changelog, BAD_REVISION);
tikhomirov@596: 		LinkedList<Integer> queue = new LinkedList<Integer>();
tikhomirov@691: 		BitSet seen = new BitSet(totalFileRevs);
tikhomirov@691: 		queue.add(fileRevTo);
tikhomirov@596: 		do {
tikhomirov@691: 			int fileRev = queue.removeFirst();
tikhomirov@691: 			int offFileRev = fileRev - fileRevFrom;
tikhomirov@691: 			if (seen.get(offFileRev)) {
tikhomirov@596: 				continue;
tikhomirov@596: 			}
tikhomirov@691: 			seen.set(offFileRev);
tikhomirov@691: 			int csetRev = df.getChangesetRevisionIndex(fileRev);
tikhomirov@691: 			if (csetRev < csetFrom || csetRev > csetTo) {
tikhomirov@691: 				continue;
tikhomirov@691: 			}
tikhomirov@691: 			fileRevsToVisit.add(fileRev);
tikhomirov@691: 
tikhomirov@691: 			file2changelog[offFileRev] = csetRev;
tikhomirov@691: 			int p1 = fileParentRevs.get(2*offFileRev);
tikhomirov@691: 			int p2 = fileParentRevs.get(2*offFileRev + 1);
tikhomirov@691: 			if (p1 != NO_REVISION && p1 >= fileRevFrom) {
tikhomirov@596: 				queue.addLast(p1);
tikhomirov@596: 			}
tikhomirov@691: 			if (p2 != NO_REVISION && p2 >= fileRevFrom) {
tikhomirov@596: 				queue.addLast(p2);
tikhomirov@596: 			}
tikhomirov@596: 		} while (!queue.isEmpty());
tikhomirov@596: 		// make sure no child is processed before we handled all (grand-)parents of the element
tikhomirov@596: 		fileRevsToVisit.sort(false);
tikhomirov@596: 	}
tikhomirov@596: 	
tikhomirov@691: 	public void linkTo(FileRevisionHistoryChunk next) {
tikhomirov@691: 		// assume that init() has been called already 
tikhomirov@691: 		if (next == null) {
tikhomirov@596: 			return;
tikhomirov@596: 		}
tikhomirov@691: 		next.originFileRev = fileRevsToVisit.get(0); // files to visit are new to old
tikhomirov@691: 		next.originChangelogRev = changeset(next.originFileRev);
tikhomirov@596: 	}
tikhomirov@596: 
tikhomirov@596: 	public int[] fileRevisions(HgIterateDirection iterateOrder) {
tikhomirov@596: 		// fileRevsToVisit is { r10, r7, r6, r5, r0 }, new to old
tikhomirov@596: 		int[] rv = fileRevsToVisit.toArray();
tikhomirov@596: 		if (iterateOrder == OldToNew) {
tikhomirov@596: 			// reverse return value
tikhomirov@596: 			for (int a = 0, b = rv.length-1; a < b; a++, b--) {
tikhomirov@596: 				int t = rv[b];
tikhomirov@596: 				rv[b] = rv[a];
tikhomirov@596: 				rv[a] = t;
tikhomirov@596: 			}
tikhomirov@596: 		}
tikhomirov@596: 		return rv;
tikhomirov@596: 	}
tikhomirov@596: 	
tikhomirov@625: 	/**
tikhomirov@625: 	 * @return number of file revisions in this chunk of its history
tikhomirov@625: 	 */
tikhomirov@625: 	public int revisionCount() {
tikhomirov@625: 		return fileRevsToVisit.size();
tikhomirov@625: 	}
tikhomirov@625: 	
tikhomirov@596: 	public int changeset(int fileRevIndex) {
tikhomirov@691: 		return file2changelog[fileRevIndex - fileRevFrom];
tikhomirov@596: 	}
tikhomirov@596: 	
tikhomirov@596: 	public void fillFileParents(int fileRevIndex, int[] fileParents) {
tikhomirov@691: 		if (fileRevIndex == fileRevFrom && originFileRev != BAD_REVISION) {
tikhomirov@596: 			// this chunk continues another file
tikhomirov@596: 			assert originFileRev != NO_REVISION;
tikhomirov@596: 			fileParents[0] = originFileRev;
tikhomirov@596: 			fileParents[1] = NO_REVISION;
tikhomirov@596: 			return;
tikhomirov@596: 		}
tikhomirov@691: 		int x = fileRevIndex - fileRevFrom;
tikhomirov@691: 		fileParents[0] = fileParentRevs.get(x * 2);
tikhomirov@691: 		fileParents[1] = fileParentRevs.get(x * 2 + 1);
tikhomirov@596: 	}
tikhomirov@596: 	
tikhomirov@596: 	public void fillCsetParents(int fileRevIndex, int[] csetParents) {
tikhomirov@691: 		if (fileRevIndex == fileRevFrom && originFileRev != BAD_REVISION) {
tikhomirov@691: 			assert originChangelogRev != NO_REVISION;
tikhomirov@596: 			csetParents[0] = originChangelogRev;
tikhomirov@596: 			csetParents[1] = NO_REVISION; // I wonder if possible to start a copy with two parents?
tikhomirov@596: 			return;
tikhomirov@596: 		}
tikhomirov@691: 		int x = fileRevIndex - fileRevFrom;
tikhomirov@691: 		int fp1 = fileParentRevs.get(x * 2);
tikhomirov@691: 		int fp2 = fileParentRevs.get(x * 2 + 1);
tikhomirov@596: 		csetParents[0] = fp1 == NO_REVISION ? NO_REVISION : changeset(fp1);
tikhomirov@596: 		csetParents[1] = fp2 == NO_REVISION ? NO_REVISION : changeset(fp2);
tikhomirov@596: 	}
tikhomirov@596: }