ReftableReader

/*
 * Copyright (C) 2017, 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.storage.reftable;

import static java.nio.charset.StandardCharsets.UTF_8;
import static org.eclipse.jgit.internal.storage.reftable.BlockReader.decodeBlockLen;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_BLOCK_TYPE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_FOOTER_LEN;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_HEADER_LEN;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.INDEX_BLOCK_TYPE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_BLOCK_TYPE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.REF_BLOCK_TYPE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VERSION_1;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.isFileHeaderMagic;
import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;

import java.io.IOException;
import java.nio.ByteBuffer;
import java.text.MessageFormat;
import java.util.Arrays;
import java.util.zip.CRC32;

import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.internal.storage.io.BlockSource;
import org.eclipse.jgit.internal.storage.reftable.BlockWriter.LogEntry;
import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.Ref;
import org.eclipse.jgit.lib.ReflogEntry;
import org.eclipse.jgit.util.LongList;
import org.eclipse.jgit.util.LongMap;
import org.eclipse.jgit.util.NB;

/**
 * Reads a reftable formatted file.
 * <p>
 * {@code ReftableReader} is not thread-safe. Concurrent readers need their own
 * instance to read from the same file.
 */
public class ReftableReader extends Reftable implements AutoCloseable {
	private final BlockSource src;

	private int blockSize = -1;
	private long minUpdateIndex;
	private long maxUpdateIndex;

	private long refEnd;
	private long objPosition;
	private long objEnd;
	private long logPosition;
	private long logEnd;
	private int objIdLen;

	private long refIndexPosition = -1;
	private long objIndexPosition = -1;
	private long logIndexPosition = -1;

	private BlockReader refIndex;
	private BlockReader objIndex;
	private BlockReader logIndex;
	private LongMap<BlockReader> indexCache;

	/**
	 * Initialize a new reftable reader.
	 *
	 * @param src
	 *            the file content to read.
	 */
	public ReftableReader(BlockSource src) {
		this.src = src;
	}

	/**
	 * Get the block size in bytes chosen for this file by the writer.
	 *
	 * @return the block size in bytes chosen for this file by the writer. Most
	 *         reads from the
	 *         {@link org.eclipse.jgit.internal.storage.io.BlockSource} will be
	 *         aligned to the block size.
	 * @throws java.io.IOException
	 *             file cannot be read.
	 */
	public int blockSize() throws IOException {
		if (blockSize == -1) {
			readFileHeader();
		}
		return blockSize;
	}

	@Override
	public boolean hasObjectMap() throws IOException {
		if (objIndexPosition == -1) {
			readFileFooter();
		}

		// We have the map, we have no refs, or the table is small.
		return (objPosition > 0 || refEnd == 24 || refIndexPosition == 0);
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public long minUpdateIndex() throws IOException {
		if (blockSize == -1) {
			readFileHeader();
		}
		return minUpdateIndex;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public long maxUpdateIndex() throws IOException {
		if (blockSize == -1) {
			readFileHeader();
		}
		return maxUpdateIndex;
	}

	/** {@inheritDoc} */
	@Override
	public RefCursor allRefs() throws IOException {
		if (blockSize == -1) {
			readFileHeader();
		}

		if (refEnd == 0) {
			readFileFooter();
		}
		src.adviseSequentialRead(0, refEnd);

		RefCursorImpl i = new RefCursorImpl(refEnd, null, false);
		i.block = readBlock(0, refEnd);
		return i;
	}

	/** {@inheritDoc} */
	@Override
	public RefCursor seekRef(String refName) throws IOException {
		initRefIndex();

		byte[] key = refName.getBytes(UTF_8);
		RefCursorImpl i = new RefCursorImpl(refEnd, key, false);
		i.block = seek(REF_BLOCK_TYPE, key, refIndex, 0, refEnd);
		return i;
	}

	/** {@inheritDoc} */
	@Override
	public RefCursor seekRefsWithPrefix(String prefix) throws IOException {
		initRefIndex();

		byte[] key = prefix.getBytes(UTF_8);
		RefCursorImpl i = new RefCursorImpl(refEnd, key, true);
		i.block = seek(REF_BLOCK_TYPE, key, refIndex, 0, refEnd);
		return i;
	}

	/** {@inheritDoc} */
	@Override
	public RefCursor byObjectId(AnyObjectId id) throws IOException {
		initObjIndex();
		ObjCursorImpl i = new ObjCursorImpl(refEnd, id);
		if (objIndex != null) {
			i.initSeek();
		} else {
			i.initScan();
		}
		return i;
	}

	/** {@inheritDoc} */
	@Override
	public LogCursor allLogs() throws IOException {
		initLogIndex();
		if (logPosition > 0) {
			src.adviseSequentialRead(logPosition, logEnd);
			LogCursorImpl i = new LogCursorImpl(logEnd, null);
			i.block = readBlock(logPosition, logEnd);
			return i;
		}
		return new EmptyLogCursor();
	}

	/** {@inheritDoc} */
	@Override
	public LogCursor seekLog(String refName, long updateIndex)
			throws IOException {
		initLogIndex();
		if (logPosition > 0) {
			byte[] key = LogEntry.key(refName, updateIndex);
			byte[] match = refName.getBytes(UTF_8);
			LogCursorImpl i = new LogCursorImpl(logEnd, match);
			i.block = seek(LOG_BLOCK_TYPE, key, logIndex, logPosition, logEnd);
			return i;
		}
		return new EmptyLogCursor();
	}

	private BlockReader seek(byte blockType, byte[] key, BlockReader idx,
			long startPos, long endPos) throws IOException {
		if (idx != null) {
			// Walk through a possibly multi-level index to a leaf block.
			BlockReader block = idx;
			do {
				if (block.seekKey(key) > 0) {
					return null;
				}
				long pos = block.readPositionFromIndex();
				block = readBlock(pos, endPos);
			} while (block.type() == INDEX_BLOCK_TYPE);
			block.seekKey(key);
			return block;
		}
		if (blockType == LOG_BLOCK_TYPE) {
			// No index. Log blocks are irregularly sized, so we can't do binary
			// search between blocks. Scan over blocks instead.
			BlockReader block = readBlock(startPos, endPos);

			for (;;) {
				if (block == null || block.type() != LOG_BLOCK_TYPE) {
					return null;
				}

				int result = block.seekKey(key);
				if (result <= 0) {
					// == 0 : we found the key.
					// < 0 : the key is before this block. Either the ref name is there
					// but only at a newer updateIndex, or it is absent. We leave it to
					// logcursor to distinguish between both cases.
					return block;
				}

				long pos = block.endPosition();
				if (pos >= endPos) {
					return null;
				}
				block = readBlock(pos, endPos);
			}
		}
		return binarySearch(blockType, key, startPos, endPos);
	}

	private BlockReader binarySearch(byte blockType, byte[] key,
			long startPos, long endPos) throws IOException {
		if (blockSize == 0) {
			BlockReader b = readBlock(startPos, endPos);
			if (blockType != b.type()) {
				return null;
			}
			b.seekKey(key);
			return b;
		}

		int low = (int) (startPos / blockSize);
		int end = blocksIn(startPos, endPos);
		BlockReader block = null;
		do {
			int mid = (low + end) >>> 1;
			block = readBlock(((long) mid) * blockSize, endPos);
			if (blockType != block.type()) {
				return null;
			}
			int cmp = block.seekKey(key);
			if (cmp < 0) {
				end = mid;
			} else if (cmp == 0) {
				break;
			} else /* if (cmp > 0) */ {
				low = mid + 1;
			}
		} while (low < end);
		return block;
	}

	private void readFileHeader() throws IOException {
		readHeaderOrFooter(0, FILE_HEADER_LEN);
	}

	private void readFileFooter() throws IOException {
		int ftrLen = FILE_FOOTER_LEN;
		byte[] ftr = readHeaderOrFooter(src.size() - ftrLen, ftrLen);

		CRC32 crc = new CRC32();
		crc.update(ftr, 0, ftrLen - 4);
		if (crc.getValue() != NB.decodeUInt32(ftr, ftrLen - 4)) {
			throw new IOException(JGitText.get().invalidReftableCRC);
		}

		refIndexPosition = NB.decodeInt64(ftr, 24);
		long p = NB.decodeInt64(ftr, 32);
		objPosition = p >>> 5;
		objIdLen = (int) (p & 0x1f);
		objIndexPosition = NB.decodeInt64(ftr, 40);
		logPosition = NB.decodeInt64(ftr, 48);
		logIndexPosition = NB.decodeInt64(ftr, 56);

		if (refIndexPosition > 0) {
			refEnd = refIndexPosition;
		} else if (objPosition > 0) {
			refEnd = objPosition;
		} else if (logPosition > 0) {
			refEnd = logPosition;
		} else {
			refEnd = src.size() - ftrLen;
		}

		if (objPosition > 0) {
			if (objIndexPosition > 0) {
				objEnd = objIndexPosition;
			} else if (logPosition > 0) {
				objEnd = logPosition;
			} else {
				objEnd = src.size() - ftrLen;
			}
		}

		if (logPosition > 0) {
			if (logIndexPosition > 0) {
				logEnd = logIndexPosition;
			} else {
				logEnd = src.size() - ftrLen;
			}
		}
	}

	private byte[] readHeaderOrFooter(long pos, int len) throws IOException {
		ByteBuffer buf = src.read(pos, len);
		if (buf.position() != len) {
			throw new IOException(JGitText.get().shortReadOfBlock);
		}

		byte[] tmp = new byte[len];
		buf.flip();
		buf.get(tmp);
		if (!isFileHeaderMagic(tmp, 0, len)) {
			throw new IOException(JGitText.get().invalidReftableFile);
		}

		int v = NB.decodeInt32(tmp, 4);
		int version = v >>> 24;
		if (VERSION_1 != version) {
			throw new IOException(MessageFormat.format(
					JGitText.get().unsupportedReftableVersion,
					Integer.valueOf(version)));
		}
		if (blockSize == -1) {
			blockSize = v & 0xffffff;
		}
		minUpdateIndex = NB.decodeInt64(tmp, 8);
		maxUpdateIndex = NB.decodeInt64(tmp, 16);
		return tmp;
	}

	private void initRefIndex() throws IOException {
		if (refIndexPosition < 0) {
			readFileFooter();
		}
		if (refIndex == null && refIndexPosition > 0) {
			refIndex = readIndex(refIndexPosition);
		}
	}

	private void initObjIndex() throws IOException {
		if (objIndexPosition < 0) {
			readFileFooter();
		}
		if (objIndex == null && objIndexPosition > 0) {
			objIndex = readIndex(objIndexPosition);
		}
	}

	private void initLogIndex() throws IOException {
		if (logIndexPosition < 0) {
			readFileFooter();
		}
		if (logIndex == null && logIndexPosition > 0) {
			logIndex = readIndex(logIndexPosition);
		}
	}

	private BlockReader readIndex(long pos) throws IOException {
		int sz = readBlockLen(pos);
		BlockReader i = new BlockReader();
		i.readBlock(src, pos, sz);
		i.verifyIndex();
		return i;
	}

	private int readBlockLen(long pos) throws IOException {
		int sz = pos == 0 ? FILE_HEADER_LEN + 4 : 4;
		ByteBuffer tmp = src.read(pos, sz);
		if (tmp.position() < sz) {
			throw new IOException(JGitText.get().invalidReftableFile);
		}
		byte[] buf;
		if (tmp.hasArray() && tmp.arrayOffset() == 0) {
			buf = tmp.array();
		} else {
			buf = new byte[sz];
			tmp.flip();
			tmp.get(buf);
		}
		if (pos == 0 && buf[FILE_HEADER_LEN] == FILE_BLOCK_TYPE) {
			return FILE_HEADER_LEN;
		}
		int p = pos == 0 ? FILE_HEADER_LEN : 0;
		return decodeBlockLen(NB.decodeInt32(buf, p));
	}

	private BlockReader readBlock(long pos, long end) throws IOException {
		if (indexCache != null) {
			BlockReader b = indexCache.get(pos);
			if (b != null) {
				return b;
			}
		}

		int sz = blockSize;
		if (sz == 0) {
			sz = readBlockLen(pos);
		} else if (pos + sz > end) {
			sz = (int) (end - pos); // last block may omit padding.
		}

		BlockReader b = new BlockReader();
		b.readBlock(src, pos, sz);
		if (b.type() == INDEX_BLOCK_TYPE) {
			if (indexCache == null) {
				indexCache = new LongMap<>();
			}
			indexCache.put(pos, b);
		}
		return b;
	}

	private int blocksIn(long pos, long end) {
		int blocks = (int) ((end - pos) / blockSize);
		return end % blockSize == 0 ? blocks : (blocks + 1);
	}

	/**
	 * Get size of the reftable, in bytes.
	 *
	 * @return size of the reftable, in bytes.
	 * @throws java.io.IOException
	 *             size cannot be obtained.
	 */
	public long size() throws IOException {
		return src.size();
	}

	/** {@inheritDoc} */
	@Override
	public void close() throws IOException {
		src.close();
	}

	private class RefCursorImpl extends RefCursor {
		private final long scanEnd;
		private final byte[] match;
		private final boolean prefix;

		private Ref ref;
		BlockReader block;

		RefCursorImpl(long scanEnd, byte[] match, boolean prefix) {
			this.scanEnd = scanEnd;
			this.match = match;
			this.prefix = prefix;
		}

		@Override
		public boolean next() throws IOException {
			for (;;) {
				if (block == null || block.type() != REF_BLOCK_TYPE) {
					return false;
				} else if (!block.next()) {
					long pos = block.endPosition();
					if (pos >= scanEnd) {
						return false;
					}
					block = readBlock(pos, scanEnd);
					continue;
				}

				block.parseKey();
				if (match != null && !block.match(match, prefix)) {
					block.skipValue();
					return false;
				}

				ref = block.readRef(minUpdateIndex);
				if (!includeDeletes && wasDeleted()) {
					continue;
				}
				return true;
			}
		}

		@Override
		public void seekPastPrefix(String prefixName) throws IOException {
			initRefIndex();
			byte[] key = prefixName.getBytes(UTF_8);
			ByteBuffer byteBuffer = ByteBuffer.allocate(key.length + 1);
			byteBuffer.put(key);
			// Add the representation of the last byte lexicographically. Based on how UTF_8
			// representation works, this byte will be bigger lexicographically than any
			// UTF_8 character when translated into bytes, since 0xFF can never be a part of
			// a UTF_8 string.
			byteBuffer.put((byte) 0xFF);

			block = seek(REF_BLOCK_TYPE, byteBuffer.array(), refIndex, 0, refEnd);
		}

		@Override
		public Ref getRef() {
			return ref;
		}

		@Override
		public void close() {
			// Do nothing.
		}
	}

	private class LogCursorImpl extends LogCursor {
		private final long scanEnd;
		private final byte[] match;

		private String refName;
		private long updateIndex;
		private ReflogEntry entry;
		BlockReader block;

		/**
		 * Scans logs from this table until scanEnd position.
		 *
		 * @param scanEnd
		 *            end of the log data in the reftable.
		 * @param match
		 *            if non-null, limits the scan to precisely that refname.
		 */
		LogCursorImpl(long scanEnd, byte[] match) {
			this.scanEnd = scanEnd;
			this.match = match;
		}

		@Override
		public boolean next() throws IOException {
			for (;;) {
				if (block == null || block.type() != LOG_BLOCK_TYPE) {
					return false;
				} else if (!block.next()) {
					long pos = block.endPosition();
					if (pos >= scanEnd) {
						return false;
					}
					block = readBlock(pos, scanEnd);
					continue;
				}

				block.parseKey();
				if (match != null && !block.match(match, false)) {
					block.skipValue();
					return false;
				}

				refName = block.name();
				updateIndex = block.readLogUpdateIndex();
				entry = block.readLogEntry();
				if (entry == null && !includeDeletes) {
					continue;
				}
				return true;
			}
		}

		@Override
		public String getRefName() {
			return refName;
		}

		@Override
		public long getUpdateIndex() {
			return updateIndex;
		}

		@Override
		public ReflogEntry getReflogEntry() {
			return entry;
		}

		@Override
		public void close() {
			// Do nothing.
		}
	}

	static final LongList EMPTY_LONG_LIST = new LongList(0);

	private class ObjCursorImpl extends RefCursor {
		private final long scanEnd;
		private final ObjectId match;

		private Ref ref;
		private int listIdx;

		private LongList blockPos;
		private BlockReader block;

		ObjCursorImpl(long scanEnd, AnyObjectId id) {
			this.scanEnd = scanEnd;
			this.match = id.copy();
		}

		void initSeek() throws IOException {
			byte[] rawId = new byte[OBJECT_ID_LENGTH];
			match.copyRawTo(rawId, 0);
			byte[] key = Arrays.copyOf(rawId, objIdLen);

			BlockReader b = objIndex;
			do {
				if (b.seekKey(key) > 0) {
					blockPos = EMPTY_LONG_LIST;
					return;
				}
				long pos = b.readPositionFromIndex();
				b = readBlock(pos, objEnd);
			} while (b.type() == INDEX_BLOCK_TYPE);
			b.seekKey(key);
			while (b.next()) {
				b.parseKey();
				if (b.match(key, false)) {
					blockPos = b.readBlockPositionList();
					if (blockPos == null) {
						initScan();
						return;
					}
					break;
				}
				b.skipValue();
			}
			if (blockPos == null) {
				blockPos = EMPTY_LONG_LIST;
			}
			if (blockPos.size() > 0) {
				long pos = blockPos.get(listIdx++);
				block = readBlock(pos, scanEnd);
			}
		}

		void initScan() throws IOException {
			block = readBlock(0, scanEnd);
		}

		@Override
		public boolean next() throws IOException {
			for (;;) {
				if (block == null || block.type() != REF_BLOCK_TYPE) {
					return false;
				} else if (!block.next()) {
					long pos;
					if (blockPos != null) {
						if (listIdx >= blockPos.size()) {
							return false;
						}
						pos = blockPos.get(listIdx++);
					} else {
						pos = block.endPosition();
					}
					if (pos >= scanEnd) {
						return false;
					}
					block = readBlock(pos, scanEnd);
					continue;
				}

				block.parseKey();
				ref = block.readRef(minUpdateIndex);
				ObjectId id = ref.getObjectId();
				if (id != null && match.equals(id)
						&& (includeDeletes || !wasDeleted())) {
					return true;
				}
			}
		}

		@Override
		/**
		 * The implementation here would not be efficient complexity-wise since it
		 * expected that there are a small number of refs that match the same object id.
		 * In such case it's better to not even use this method (as the caller might
		 * expect it to be efficient).
		 */
		public void seekPastPrefix(String prefixName) throws IOException {
		    throw new UnsupportedOperationException();
		}

		@Override
		public Ref getRef() {
			return ref;
		}

		@Override
		public void close() {
			// Do nothing.
		}
	}
}