| /* |
| * Copyright (C) 2016, Google Inc. and others |
| * |
| * This program and the accompanying materials are made available under the |
| * terms of the Eclipse Distribution License v. 1.0 which is available at |
| * https://www.eclipse.org/org/documents/edl-v10.php. |
| * |
| * SPDX-License-Identifier: BSD-3-Clause |
| */ |
| |
| package org.eclipse.jgit.internal.ketch; |
| |
| import static org.eclipse.jgit.lib.FileMode.TYPE_GITLINK; |
| |
| import java.io.IOException; |
| import java.util.ArrayList; |
| import java.util.HashSet; |
| import java.util.List; |
| import java.util.Set; |
| |
| import org.eclipse.jgit.annotations.Nullable; |
| import org.eclipse.jgit.lib.AnyObjectId; |
| import org.eclipse.jgit.lib.CommitBuilder; |
| import org.eclipse.jgit.lib.ObjectId; |
| import org.eclipse.jgit.lib.ObjectInserter; |
| import org.eclipse.jgit.lib.PersonIdent; |
| import org.eclipse.jgit.lib.Repository; |
| import org.eclipse.jgit.revwalk.RevCommit; |
| import org.eclipse.jgit.revwalk.RevObject; |
| import org.eclipse.jgit.revwalk.RevWalk; |
| import org.eclipse.jgit.transport.ReceiveCommand; |
| import org.eclipse.jgit.treewalk.EmptyTreeIterator; |
| import org.eclipse.jgit.treewalk.TreeWalk; |
| import org.eclipse.jgit.treewalk.filter.TreeFilter; |
| |
| /** |
| * Constructs a set of commands to stage content during a proposal. |
| */ |
| public class StageBuilder { |
| /** |
| * Acceptable number of references to send in a single stage transaction. |
| * <p> |
| * If the number of unique objects exceeds this amount the builder will |
| * attempt to decrease the reference count by chaining commits.. |
| */ |
| private static final int SMALL_BATCH_SIZE = 5; |
| |
| /** |
| * Acceptable number of commits to chain together using parent pointers. |
| * <p> |
| * When staging many unique commits the {@link StageBuilder} batches |
| * together unrelated commits as parents of a temporary commit. After the |
| * proposal completes the temporary commit is discarded and can be garbage |
| * collected by all replicas. |
| */ |
| private static final int TEMP_PARENT_BATCH_SIZE = 128; |
| |
| private static final byte[] PEEL = { ' ', '^' }; |
| |
| private final String txnStage; |
| private final String txnId; |
| |
| /** |
| * Construct a stage builder for a transaction. |
| * |
| * @param txnStageNamespace |
| * namespace for transaction references to build |
| * {@code "txnStageNamespace/txnId.n"} style names. |
| * @param txnId |
| * identifier used to name temporary staging refs. |
| */ |
| public StageBuilder(String txnStageNamespace, ObjectId txnId) { |
| this.txnStage = txnStageNamespace; |
| this.txnId = txnId.name(); |
| } |
| |
| /** |
| * Compare two RefTrees and return commands to stage new objects. |
| * <p> |
| * This method ignores the lineage between the two RefTrees and does a |
| * straight diff on the two trees. New objects will be staged. The diff |
| * strategy is useful to catch-up a lagging replica, without sending every |
| * intermediate step. This may mean the replica does not have the same |
| * object set as other replicas if there are rewinds or branch deletes. |
| * |
| * @param git |
| * source repository to read {@code oldTree} and {@code newTree} |
| * from. |
| * @param oldTree |
| * accepted RefTree on the replica ({@code refs/txn/accepted}). |
| * Use {@link org.eclipse.jgit.lib.ObjectId#zeroId()} if the |
| * remote does not have any ref tree, e.g. a new replica catching |
| * up. |
| * @param newTree |
| * RefTree being sent to the replica. The trees will be compared. |
| * @return list of commands to create {@code "refs/txn/stage/..."} |
| * references on replicas anchoring new objects into the repository |
| * while a transaction gains consensus. |
| * @throws java.io.IOException |
| * {@code git} cannot be accessed to compare {@code oldTree} and |
| * {@code newTree} to build the object set. |
| */ |
| public List<ReceiveCommand> makeStageList(Repository git, ObjectId oldTree, |
| ObjectId newTree) throws IOException { |
| try (RevWalk rw = new RevWalk(git); |
| TreeWalk tw = new TreeWalk(rw.getObjectReader()); |
| ObjectInserter ins = git.newObjectInserter()) { |
| if (AnyObjectId.isEqual(oldTree, ObjectId.zeroId())) { |
| tw.addTree(new EmptyTreeIterator()); |
| } else { |
| tw.addTree(rw.parseTree(oldTree)); |
| } |
| tw.addTree(rw.parseTree(newTree)); |
| tw.setFilter(TreeFilter.ANY_DIFF); |
| tw.setRecursive(true); |
| |
| Set<ObjectId> newObjs = new HashSet<>(); |
| while (tw.next()) { |
| if (tw.getRawMode(1) == TYPE_GITLINK |
| && !tw.isPathSuffix(PEEL, 2)) { |
| newObjs.add(tw.getObjectId(1)); |
| } |
| } |
| |
| List<ReceiveCommand> cmds = makeStageList(newObjs, git, ins); |
| ins.flush(); |
| return cmds; |
| } |
| } |
| |
| /** |
| * Construct a set of commands to stage objects on a replica. |
| * |
| * @param newObjs |
| * objects to send to a replica. |
| * @param git |
| * local repository to read source objects from. Required to |
| * perform minification of {@code newObjs}. |
| * @param inserter |
| * inserter to write temporary commit objects during minification |
| * if many new branches are created by {@code newObjs}. |
| * @return list of commands to create {@code "refs/txn/stage/..."} |
| * references on replicas anchoring {@code newObjs} into the |
| * repository while a transaction gains consensus. |
| * @throws java.io.IOException |
| * {@code git} cannot be accessed to perform minification of |
| * {@code newObjs}. |
| */ |
| public List<ReceiveCommand> makeStageList(Set<ObjectId> newObjs, |
| @Nullable Repository git, @Nullable ObjectInserter inserter) |
| throws IOException { |
| if (git == null || newObjs.size() <= SMALL_BATCH_SIZE) { |
| // Without a source repository can only construct unique set. |
| List<ReceiveCommand> cmds = new ArrayList<>(newObjs.size()); |
| for (ObjectId id : newObjs) { |
| stage(cmds, id); |
| } |
| return cmds; |
| } |
| |
| List<ReceiveCommand> cmds = new ArrayList<>(); |
| List<RevCommit> commits = new ArrayList<>(); |
| reduceObjects(cmds, commits, git, newObjs); |
| |
| if (inserter == null || commits.size() <= 1 |
| || (cmds.size() + commits.size()) <= SMALL_BATCH_SIZE) { |
| // Without an inserter to aggregate commits, or for a small set of |
| // commits just send one stage ref per commit. |
| for (RevCommit c : commits) { |
| stage(cmds, c.copy()); |
| } |
| return cmds; |
| } |
| |
| // 'commits' is sorted most recent to least recent commit. |
| // Group batches of commits and build a chain. |
| // TODO(sop) Cluster by restricted graphs to support filtering. |
| ObjectId tip = null; |
| for (int end = commits.size(); end > 0;) { |
| int start = Math.max(0, end - TEMP_PARENT_BATCH_SIZE); |
| List<RevCommit> batch = commits.subList(start, end); |
| List<ObjectId> parents = new ArrayList<>(1 + batch.size()); |
| if (tip != null) { |
| parents.add(tip); |
| } |
| parents.addAll(batch); |
| |
| CommitBuilder b = new CommitBuilder(); |
| b.setTreeId(batch.get(0).getTree()); |
| b.setParentIds(parents); |
| b.setAuthor(tmpAuthor(batch)); |
| b.setCommitter(b.getAuthor()); |
| tip = inserter.insert(b); |
| end = start; |
| } |
| stage(cmds, tip); |
| return cmds; |
| } |
| |
| private static PersonIdent tmpAuthor(List<RevCommit> commits) { |
| // Construct a predictable author using most recent commit time. |
| int t = 0; |
| for (int i = 0; i < commits.size();) { |
| t = Math.max(t, commits.get(i).getCommitTime()); |
| } |
| String name = "Ketch Stage"; //$NON-NLS-1$ |
| String email = "tmp@tmp"; //$NON-NLS-1$ |
| return new PersonIdent(name, email, t * 1000L, 0); |
| } |
| |
| private void reduceObjects(List<ReceiveCommand> cmds, |
| List<RevCommit> commits, Repository git, |
| Set<ObjectId> newObjs) throws IOException { |
| try (RevWalk rw = new RevWalk(git)) { |
| rw.setRetainBody(false); |
| |
| for (ObjectId id : newObjs) { |
| RevObject obj = rw.parseAny(id); |
| if (obj instanceof RevCommit) { |
| rw.markStart((RevCommit) obj); |
| } else { |
| stage(cmds, id); |
| } |
| } |
| |
| for (RevCommit c; (c = rw.next()) != null;) { |
| commits.add(c); |
| rw.markUninteresting(c); |
| } |
| } |
| } |
| |
| private void stage(List<ReceiveCommand> cmds, ObjectId id) { |
| int estLen = txnStage.length() + txnId.length() + 5; |
| StringBuilder n = new StringBuilder(estLen); |
| n.append(txnStage).append(txnId).append('.'); |
| n.append(Integer.toHexString(cmds.size())); |
| cmds.add(new ReceiveCommand(ObjectId.zeroId(), id, n.toString())); |
| } |
| } |