aboutsummaryrefslogtreecommitdiffstats
path: root/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraph.java
blob: d1178c28502e24881ac8d676e10e1de7dd4d3c06 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/*
 * Copyright (C) 2022, Tencent.
 *
 * 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.storage.commitgraph;

import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.ObjectId;

/**
 * The CommitGraph is a supplemental data structure that accelerates commit
 * graph walks.
 * <p>
 * If a user downgrades or disables the <code>core.commitGraph</code> config
 * setting, then the existing object database is sufficient.
 * </p>
 * <p>
 * It stores the commit graph structure along with some extra metadata to speed
 * up graph walks. By listing commit OIDs in lexicographic order, we can
 * identify an integer position for each commit and refer to the parents of a
 * commit using those integer positions. We use binary search to find initial
 * commits and then use the integer positions for fast lookups during the walk.
 * </p>
 */
public interface CommitGraph {

	/** Empty {@link CommitGraph} with no results. */
	CommitGraph EMPTY = new CommitGraph() {
		@Override
		public int findGraphPosition(AnyObjectId commit) {
			return -1;
		}

		@Override
		public CommitData getCommitData(int graphPos) {
			return null;
		}

		@Override
		public ObjectId getObjectId(int graphPos) {
			return null;
		}

		@Override
		public ChangedPathFilter getChangedPathFilter(int graphPos) {
			return null;
		}

		@Override
		public long getCommitCnt() {
			return 0;
		}
	};

	/**
	 * Find the position in the commit-graph of the commit.
	 * <p>
	 * The position can only be used within the CommitGraph Instance you got it
	 * from. That's because the graph position of the same commit may be
	 * different in CommitGraph obtained at different times (eg., regenerated
	 * new commit-graph).
	 *
	 * @param commit
	 *            the commit for which the commit-graph position will be found.
	 * @return the commit-graph position or -1 if the object was not found.
	 */
	int findGraphPosition(AnyObjectId commit);

	/**
	 * Get the metadata of a commit。
	 * <p>
	 * This function runs in time O(1).
	 * <p>
	 * In the process of commit history traversal,
	 * {@link CommitData#getParents()} makes us get the graphPos of the commit's
	 * parents in advance, so that we can avoid O(logN) lookup and use O(1)
	 * lookup instead.
	 *
	 * @param graphPos
	 *            the position in the commit-graph of the object.
	 * @return the metadata of a commit or null if it's not found.
	 */
	CommitData getCommitData(int graphPos);

	/**
	 * Get the object at the commit-graph position.
	 *
	 * @param graphPos
	 *            the position in the commit-graph of the object.
	 * @return the ObjectId or null if it's not found.
	 */
	ObjectId getObjectId(int graphPos);

	/**
	 * Get the changed path filter of the object at the commit-graph position.
	 *
	 * @param graphPos
	 *            the position in the commit-graph of the object.
	 * @return the bloom filter or null if it's not found.
	 */
	ChangedPathFilter getChangedPathFilter(int graphPos);

	/**
	 * Obtain the total number of commits described by this commit-graph.
	 *
	 * @return number of commits in this commit-graph.
	 */
	long getCommitCnt();

	/**
	 * Metadata of a commit in commit data chunk.
	 */
	interface CommitData {

		/**
		 * Get a reference to this commit's tree.
		 *
		 * @return tree of this commit.
		 */
		ObjectId getTree();

		/**
		 * Obtain an array of all parents.
		 * <p>
		 * The method only provides the graph positions of parents in
		 * commit-graph, call {@link CommitGraph#getObjectId(int)} to get the
		 * real objectId.
		 *
		 * @return the array of parents.
		 */
		int[] getParents();

		/**
		 * Time from the "committer" line.
		 *
		 * @return the commit time in seconds since EPOCH.
		 */
		long getCommitTime();

		/**
		 * Get the generation number (the distance from the root) of the commit.
		 *
		 * @return the generation number or
		 *         {@link org.eclipse.jgit.lib.Constants#COMMIT_GENERATION_NOT_COMPUTED}
		 *         if the writer didn't calculate it.
		 */
		int getGeneration();
	}
}