tikhomirov@220: /* tikhomirov@610: * Copyright (c) 2011-2013 TMate Software Ltd tikhomirov@220: * tikhomirov@220: * This program is free software; you can redistribute it and/or modify tikhomirov@220: * it under the terms of the GNU General Public License as published by tikhomirov@220: * the Free Software Foundation; version 2 of the License. tikhomirov@220: * tikhomirov@220: * This program is distributed in the hope that it will be useful, tikhomirov@220: * but WITHOUT ANY WARRANTY; without even the implied warranty of tikhomirov@220: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the tikhomirov@220: * GNU General Public License for more details. tikhomirov@220: * tikhomirov@220: * For information on how to redistribute this software under tikhomirov@220: * the terms of a license other than GNU General Public License tikhomirov@220: * contact TMate Software at support@hg4j.com tikhomirov@220: */ tikhomirov@220: package org.tmatesoft.hg.repo; tikhomirov@220: tikhomirov@456: import static org.tmatesoft.hg.util.LogFacility.Severity.Error; tikhomirov@456: import static org.tmatesoft.hg.util.LogFacility.Severity.Warn; tikhomirov@456: tikhomirov@236: import java.io.BufferedReader; tikhomirov@244: import java.io.BufferedWriter; tikhomirov@236: import java.io.File; tikhomirov@236: import java.io.FileReader; tikhomirov@244: import java.io.FileWriter; tikhomirov@236: import java.io.IOException; tikhomirov@315: import java.util.ArrayList; tikhomirov@220: import java.util.Arrays; tikhomirov@220: import java.util.Collections; tikhomirov@220: import java.util.HashMap; tikhomirov@308: import java.util.LinkedHashMap; tikhomirov@236: import java.util.LinkedHashSet; tikhomirov@220: import java.util.LinkedList; tikhomirov@220: import java.util.List; tikhomirov@220: import java.util.Map; tikhomirov@220: import java.util.TreeMap; tikhomirov@236: import java.util.regex.Pattern; tikhomirov@220: tikhomirov@220: import org.tmatesoft.hg.core.Nodeid; tikhomirov@610: import org.tmatesoft.hg.internal.ChangelogMonitor; tikhomirov@244: import org.tmatesoft.hg.internal.Experimental; tikhomirov@628: import org.tmatesoft.hg.internal.FileUtils; tikhomirov@490: import org.tmatesoft.hg.internal.Internals; tikhomirov@220: import org.tmatesoft.hg.repo.HgChangelog.RawChangeset; tikhomirov@220: import org.tmatesoft.hg.util.ProgressSupport; tikhomirov@220: tikhomirov@220: /** tikhomirov@220: * tikhomirov@220: * @author Artem Tikhomirov tikhomirov@220: * @author TMate Software Ltd. tikhomirov@220: */ tikhomirov@220: public class HgBranches { tikhomirov@220: tikhomirov@610: private final Internals internalRepo; tikhomirov@610: private final ChangelogMonitor repoChangeTracker; tikhomirov@220: private final Map branches = new TreeMap(); tikhomirov@244: private boolean isCacheActual = false; tikhomirov@244: tikhomirov@490: HgBranches(Internals internals) { tikhomirov@490: internalRepo = internals; tikhomirov@610: repoChangeTracker = new ChangelogMonitor(internals.getRepo()); tikhomirov@220: } tikhomirov@220: tikhomirov@348: private int readCache() { tikhomirov@610: final HgRepository repo = internalRepo.getRepo(); tikhomirov@244: File branchheadsCache = getCacheFile(); tikhomirov@236: int lastInCache = -1; tikhomirov@236: if (!branchheadsCache.canRead()) { tikhomirov@236: return lastInCache; tikhomirov@236: } tikhomirov@628: BufferedReader br = null; // TODO replace with LineReader tikhomirov@236: final Pattern spacePattern = Pattern.compile(" "); tikhomirov@236: try { tikhomirov@308: final LinkedHashMap> branchHeads = new LinkedHashMap>(); tikhomirov@236: br = new BufferedReader(new FileReader(branchheadsCache)); tikhomirov@236: String line = br.readLine(); tikhomirov@236: if (line == null || line.trim().length() == 0) { tikhomirov@236: return lastInCache; tikhomirov@236: } tikhomirov@236: String[] cacheIdentity = spacePattern.split(line.trim()); tikhomirov@236: lastInCache = Integer.parseInt(cacheIdentity[1]); tikhomirov@340: final int lastKnownRepoRevIndex = repo.getChangelog().getLastRevision(); tikhomirov@340: if (lastInCache > lastKnownRepoRevIndex || !repo.getChangelog().getRevision(lastKnownRepoRevIndex).equals(Nodeid.fromAscii(cacheIdentity[0]))) { tikhomirov@340: // there are chances cache file got invalid entries due to e.g. rollback operation tikhomirov@340: return -1; tikhomirov@340: } tikhomirov@236: while ((line = br.readLine()) != null) { tikhomirov@244: String[] elements = spacePattern.split(line.trim()); tikhomirov@308: if (elements.length != 2) { tikhomirov@236: // bad entry tikhomirov@236: continue; tikhomirov@236: } tikhomirov@236: // I assume split returns substrings of the original string, hence copy of a branch name tikhomirov@236: String branchName = new String(elements[elements.length-1]); tikhomirov@308: List heads = branchHeads.get(elements[1]); tikhomirov@308: if (heads == null) { tikhomirov@308: branchHeads.put(branchName, heads = new LinkedList()); tikhomirov@308: } tikhomirov@308: heads.add(Nodeid.fromAscii(elements[0])); tikhomirov@308: } tikhomirov@308: for (Map.Entry> e : branchHeads.entrySet()) { tikhomirov@308: Nodeid[] heads = e.getValue().toArray(new Nodeid[e.getValue().size()]); tikhomirov@308: BranchInfo bi = new BranchInfo(e.getKey(), heads); tikhomirov@308: branches.put(e.getKey(), bi); tikhomirov@236: } tikhomirov@236: return lastInCache; tikhomirov@236: } catch (IOException ex) { tikhomirov@348: // log error, but otherwise do nothing tikhomirov@490: repo.getSessionContext().getLog().dump(getClass(), Warn, ex, null); tikhomirov@348: // FALL THROUGH to return -1 indicating no cache information tikhomirov@348: } catch (NumberFormatException ex) { tikhomirov@490: repo.getSessionContext().getLog().dump(getClass(), Warn, ex, null); tikhomirov@348: // FALL THROUGH tikhomirov@628: } catch (HgRuntimeException ex) { tikhomirov@628: // if happens, log error and pretend there's no cache tikhomirov@490: repo.getSessionContext().getLog().dump(getClass(), Error, ex, null); tikhomirov@354: // FALL THROUGH tikhomirov@236: } finally { tikhomirov@628: new FileUtils(repo.getSessionContext().getLog()).closeQuietly(br); tikhomirov@236: } tikhomirov@236: return -1; // deliberately not lastInCache, to avoid anything but -1 when 1st line was read and there's error is in lines 2..end tikhomirov@236: } tikhomirov@236: tikhomirov@628: void collect(final ProgressSupport ps) throws HgRuntimeException { tikhomirov@236: branches.clear(); tikhomirov@610: final HgRepository repo = internalRepo.getRepo(); tikhomirov@220: ps.start(1 + repo.getChangelog().getRevisionCount() * 2); tikhomirov@236: // tikhomirov@236: int lastCached = readCache(); tikhomirov@244: isCacheActual = lastCached == repo.getChangelog().getLastRevision(); tikhomirov@244: if (!isCacheActual) { tikhomirov@432: final HgParentChildMap pw = new HgParentChildMap(repo.getChangelog()); tikhomirov@236: pw.init(); tikhomirov@236: ps.worked(repo.getChangelog().getRevisionCount()); tikhomirov@308: // first revision branch found at tikhomirov@236: final HashMap branchStart = new HashMap(); tikhomirov@308: // last revision seen for the branch tikhomirov@236: final HashMap branchLastSeen = new HashMap(); tikhomirov@308: // revisions from the branch that have no children at all tikhomirov@236: final HashMap> branchHeads = new HashMap>(); tikhomirov@309: // revisions that are immediate children of a node from a given branch tikhomirov@309: // after iteration, there are some revisions left in this map (children of a branch last revision tikhomirov@309: // that doesn't belong to the branch. No use of this now, perhaps can deduce isInactive (e.g.those tikhomirov@309: // branches that have non-empty candidates are inactive if all their heads are roots for those left) tikhomirov@308: final HashMap> branchHeadCandidates = new HashMap>(); tikhomirov@236: HgChangelog.Inspector insp = new HgChangelog.Inspector() { tikhomirov@236: tikhomirov@236: public void next(int revisionNumber, Nodeid nodeid, RawChangeset cset) { tikhomirov@236: String branchName = cset.branch(); tikhomirov@236: if (!branchStart.containsKey(branchName)) { tikhomirov@236: branchStart.put(branchName, nodeid); tikhomirov@236: branchHeads.put(branchName, new LinkedList()); tikhomirov@308: branchHeadCandidates.put(branchName, new LinkedList()); tikhomirov@236: } else { tikhomirov@308: final List headCandidates = branchHeadCandidates.get(branchName); tikhomirov@308: if (headCandidates.remove(nodeid)) { tikhomirov@309: // likely we don't need to keep parent anymore, as we found at least 1 child thereof to be at the same branch tikhomirov@309: // however, it's possible the child we found is a result of an earlier fork, and revision in the tikhomirov@309: // branchLastSeen is 'parallel' head, which needs to be kept tikhomirov@309: Nodeid lastSeenInBranch = branchLastSeen.get(branchName); tikhomirov@309: // check if current revision is on descendant line. Seems direct parents check is enough tikhomirov@309: if (pw.safeFirstParent(nodeid).equals(lastSeenInBranch) || pw.safeSecondParent(nodeid).equals(lastSeenInBranch)) { tikhomirov@309: branchLastSeen.remove(branchName); tikhomirov@309: } tikhomirov@236: } tikhomirov@236: } tikhomirov@308: List immediateChildren = pw.directChildren(nodeid); tikhomirov@308: if (immediateChildren.size() > 0) { tikhomirov@308: // 1) children may be in another branch tikhomirov@308: // and unless we later came across another element from this branch, tikhomirov@308: // we need to record all these as potential heads tikhomirov@308: // tikhomirov@308: // 2) head1 with children in different branch, and head2 in this branch without children tikhomirov@308: branchLastSeen.put(branchName, nodeid); tikhomirov@308: branchHeadCandidates.get(branchName).addAll(immediateChildren); tikhomirov@308: } else { tikhomirov@308: // no more children known for this node, it's (one of the) head of the branch tikhomirov@308: branchHeads.get(branchName).add(nodeid); tikhomirov@308: } tikhomirov@236: ps.worked(1); tikhomirov@236: } tikhomirov@236: }; tikhomirov@236: repo.getChangelog().range(lastCached == -1 ? 0 : lastCached+1, HgRepository.TIP, insp); tikhomirov@308: // those last seen revisions from the branch that had no children from the same branch are heads. tikhomirov@236: for (String bn : branchLastSeen.keySet()) { tikhomirov@308: // these are inactive branches? - there were children, but not from the same branch? tikhomirov@236: branchHeads.get(bn).add(branchLastSeen.get(bn)); tikhomirov@236: } tikhomirov@236: for (String bn : branchStart.keySet()) { tikhomirov@236: BranchInfo bi = branches.get(bn); tikhomirov@236: if (bi != null) { tikhomirov@236: // although heads from cache shall not intersect with heads after lastCached, tikhomirov@236: // use of LHS doesn't hurt (and makes sense e.g. if cache is not completely correct in my tests) tikhomirov@236: LinkedHashSet heads = new LinkedHashSet(bi.getHeads()); tikhomirov@236: for (Nodeid oldHead : bi.getHeads()) { tikhomirov@236: // XXX perhaps, need pw.canReach(Nodeid from, Collection to) tikhomirov@236: List newChildren = pw.childrenOf(Collections.singletonList(oldHead)); tikhomirov@236: if (!newChildren.isEmpty()) { tikhomirov@236: // likely not a head any longer, tikhomirov@236: // check if any new head can be reached from old one, and, if yes, tikhomirov@236: // do not consider that old head as head. tikhomirov@236: for (Nodeid newHead : branchHeads.get(bn)) { tikhomirov@236: if (newChildren.contains(newHead)) { tikhomirov@236: heads.remove(oldHead); tikhomirov@236: break; tikhomirov@236: } tikhomirov@236: } tikhomirov@236: } // else - oldHead still head for the branch tikhomirov@236: } tikhomirov@236: heads.addAll(branchHeads.get(bn)); tikhomirov@308: bi = new BranchInfo(bn, bi.getStart(), heads.toArray(new Nodeid[0])); tikhomirov@236: } else { tikhomirov@236: Nodeid[] heads = branchHeads.get(bn).toArray(new Nodeid[0]); tikhomirov@308: bi = new BranchInfo(bn, branchStart.get(bn), heads); tikhomirov@236: } tikhomirov@236: branches.put(bn, bi); tikhomirov@236: } tikhomirov@220: } tikhomirov@308: final HgChangelog clog = repo.getChangelog(); tikhomirov@433: final HgRevisionMap rmap = new HgRevisionMap(clog).init(); tikhomirov@308: for (BranchInfo bi : branches.values()) { tikhomirov@308: bi.validate(clog, rmap); tikhomirov@308: } tikhomirov@610: repoChangeTracker.touch(); tikhomirov@220: ps.done(); tikhomirov@220: } tikhomirov@220: tikhomirov@610: public List getAllBranches() throws HgInvalidControlFileException { tikhomirov@220: return new LinkedList(branches.values()); tikhomirov@220: tikhomirov@220: } tikhomirov@220: tikhomirov@610: public BranchInfo getBranch(String name) throws HgInvalidControlFileException { tikhomirov@220: return branches.get(name); tikhomirov@220: } tikhomirov@244: tikhomirov@244: /** tikhomirov@244: * Writes down information about repository branches in a format Mercurial native client can understand. tikhomirov@244: * Cache file gets overwritten only if it is out of date (i.e. misses some branch information) tikhomirov@354: * @throws IOException if write to cache file failed tikhomirov@423: * @throws HgRuntimeException subclass thereof to indicate issues with the library. Runtime exception tikhomirov@244: */ tikhomirov@244: @Experimental(reason="Usage of cache isn't supposed to be public knowledge") tikhomirov@423: public void writeCache() throws IOException, HgRuntimeException { tikhomirov@244: if (isCacheActual) { tikhomirov@244: return; tikhomirov@244: } tikhomirov@354: File branchheadsCache = getCacheFile(); tikhomirov@354: if (!branchheadsCache.exists()) { tikhomirov@354: branchheadsCache.getParentFile().mkdirs(); // just in case cache/ doesn't exist jet tikhomirov@354: branchheadsCache.createNewFile(); tikhomirov@354: } tikhomirov@354: if (!branchheadsCache.canWrite()) { tikhomirov@354: return; tikhomirov@354: } tikhomirov@610: final HgRepository repo = internalRepo.getRepo(); tikhomirov@354: final int lastRev = repo.getChangelog().getLastRevision(); tikhomirov@354: final Nodeid lastNid = repo.getChangelog().getRevision(lastRev); tikhomirov@354: BufferedWriter bw = new BufferedWriter(new FileWriter(branchheadsCache)); tikhomirov@354: bw.write(lastNid.toString()); tikhomirov@354: bw.write((int) ' '); tikhomirov@354: bw.write(Integer.toString(lastRev)); tikhomirov@354: bw.write("\n"); tikhomirov@354: for (BranchInfo bi : branches.values()) { tikhomirov@354: for (Nodeid nid : bi.getHeads()) { tikhomirov@354: bw.write(nid.toString()); tikhomirov@354: bw.write((int) ' '); tikhomirov@354: bw.write(bi.getName()); tikhomirov@354: bw.write("\n"); tikhomirov@244: } tikhomirov@244: } tikhomirov@354: bw.close(); tikhomirov@244: } tikhomirov@244: tikhomirov@244: private File getCacheFile() { tikhomirov@244: // prior to 1.8 used to be .hg/branchheads.cache tikhomirov@490: return internalRepo.getFileFromRepoDir("cache/branchheads"); tikhomirov@244: } tikhomirov@610: tikhomirov@628: /*package-local*/ void reloadIfChanged(ProgressSupport ps) throws HgRuntimeException { tikhomirov@610: if (repoChangeTracker.isChanged()) { tikhomirov@610: collect(ps); tikhomirov@610: } tikhomirov@610: } tikhomirov@244: tikhomirov@220: public static class BranchInfo { tikhomirov@220: private final String name; tikhomirov@308: private List heads; tikhomirov@308: private boolean closed; tikhomirov@220: private final Nodeid start; tikhomirov@315: private List closedHeads; // subset of heads, those that bear 'closed' flag, or null if closed == true tikhomirov@220: tikhomirov@236: // XXX in fact, few but not all branchHeads might be closed, and isClosed for whole branch is not tikhomirov@236: // possible to determine. tikhomirov@308: BranchInfo(String branchName, Nodeid first, Nodeid[] branchHeads) { tikhomirov@220: name = branchName; tikhomirov@220: start = first; tikhomirov@308: heads = Arrays.asList(branchHeads); tikhomirov@220: } tikhomirov@236: tikhomirov@236: // incomplete branch, there's not enough information at the time of creation. shall be replaced with tikhomirov@236: // proper BI in #collect() tikhomirov@236: BranchInfo(String branchName, Nodeid[] branchHeads) { tikhomirov@308: this(branchName, Nodeid.NULL, branchHeads); tikhomirov@308: } tikhomirov@308: tikhomirov@628: void validate(HgChangelog clog, HgRevisionMap rmap) throws HgRuntimeException { tikhomirov@308: int[] localCset = new int[heads.size()]; tikhomirov@308: int i = 0; tikhomirov@308: for (Nodeid h : heads) { tikhomirov@367: localCset[i++] = rmap.revisionIndex(h); tikhomirov@308: } tikhomirov@308: // [0] tipmost, [1] tipmost open tikhomirov@308: final Nodeid[] tipmost = new Nodeid[] {null, null}; tikhomirov@308: final boolean[] allClosed = new boolean[] { true }; tikhomirov@315: final ArrayList _closedHeads = new ArrayList(heads.size()); tikhomirov@308: clog.range(new HgChangelog.Inspector() { tikhomirov@308: tikhomirov@308: public void next(int revisionNumber, Nodeid nodeid, RawChangeset cset) { tikhomirov@308: assert heads.contains(nodeid); tikhomirov@308: tipmost[0] = nodeid; tikhomirov@308: if (!"1".equals(cset.extras().get("close"))) { tikhomirov@308: tipmost[1] = nodeid; tikhomirov@308: allClosed[0] = false; tikhomirov@315: } else { tikhomirov@315: _closedHeads.add(nodeid); tikhomirov@308: } tikhomirov@308: } tikhomirov@308: }, localCset); tikhomirov@308: closed = allClosed[0]; tikhomirov@308: Nodeid[] outcome = new Nodeid[localCset.length]; tikhomirov@308: i = 0; tikhomirov@308: if (!closed && tipmost[1] != null) { tikhomirov@308: outcome[i++] = tipmost[1]; tikhomirov@308: if (i < outcome.length && !tipmost[0].equals(tipmost[1])) { tikhomirov@308: outcome[i++] = tipmost[0]; tikhomirov@308: } tikhomirov@308: } else { tikhomirov@308: outcome[i++] = tipmost[0]; tikhomirov@308: } tikhomirov@308: for (Nodeid h : heads) { tikhomirov@308: if (!h.equals(tipmost[0]) && !h.equals(tipmost[1])) { tikhomirov@308: outcome[i++] = h; tikhomirov@308: } tikhomirov@308: } tikhomirov@308: heads = Arrays.asList(outcome); tikhomirov@315: if (closed) { tikhomirov@315: // no need tikhomirov@315: closedHeads = null; tikhomirov@315: } else { tikhomirov@315: _closedHeads.trimToSize(); tikhomirov@315: closedHeads = _closedHeads; tikhomirov@315: } tikhomirov@236: } tikhomirov@220: tikhomirov@220: public String getName() { tikhomirov@220: return name; tikhomirov@220: } tikhomirov@308: /** tikhomirov@308: * @return true if all heads of this branch are marked as closed tikhomirov@308: */ tikhomirov@308: public boolean isClosed() { tikhomirov@220: return closed; tikhomirov@220: } tikhomirov@315: tikhomirov@315: /** tikhomirov@315: * @return all heads for the branch, both open and closed, tip-most head first tikhomirov@315: */ tikhomirov@220: public List getHeads() { tikhomirov@220: return heads; tikhomirov@220: } tikhomirov@315: tikhomirov@315: /** tikhomirov@315: * tikhomirov@315: * @param head one of revision from {@link #getHeads() heads} of this branch tikhomirov@315: * @return true if this particular head is closed tikhomirov@315: * @throws IllegalArgumentException if argument is not from {@link #getHeads() heads} of this branch tikhomirov@315: */ tikhomirov@315: public boolean isClosed(Nodeid head) { tikhomirov@315: if (!heads.contains(head)) { tikhomirov@315: throw new IllegalArgumentException(String.format("Revision %s does not belong to heads of %s branch", head, name), null); tikhomirov@315: } tikhomirov@315: if (closed) { tikhomirov@315: return true; tikhomirov@315: } tikhomirov@315: return closedHeads.contains(head); tikhomirov@315: } tikhomirov@220: // public Nodeid getTip() { tikhomirov@220: // } tikhomirov@236: /*public*/ Nodeid getStart() { tikhomirov@220: // first node where branch appears tikhomirov@220: return start; tikhomirov@220: } tikhomirov@220: } tikhomirov@220: }