org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ChunkWriter.java

/*
 * Copyright (C) 2017, Google Inc.
 * and other copyright owners as documented in the project's IP log.
 *
 * This program and the accompanying materials are made available
 * under the terms of the Eclipse Distribution License v1.0 which
 * accompanies this distribution, is reproduced below, and is
 * available at http://www.eclipse.org/org/documents/edl-v10.php
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following
 * conditions are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * - Redistributions in binary form must reproduce the above
 *   copyright notice, this list of conditions and the following
 *   disclaimer in the documentation and/or other materials provided
 *   with the distribution.
 *
 * - Neither the name of the Eclipse Foundation, Inc. nor the
 *   names of its contributors may be used to endorse or promote
 *   products derived from this software without specific prior
 *   written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package org.eclipse.jgit.internal.storage.reftable;

import static java.nio.charset.StandardCharsets.UTF_8;
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.OBJ_BLOCK_TYPE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.REF_BLOCK_TYPE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_1ID;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_2ID;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_LOG_RECORD;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_NONE;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_TEXT;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_TYPE_MASK;
import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.reverseUpdateIndex;
import static org.eclipse.jgit.internal.storage.reftable.ReftableOutputStream.computeVarintSize;
import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;
import static org.eclipse.jgit.lib.Ref.Storage.NEW;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.PersonIdent;
import org.eclipse.jgit.lib.Ref;
import org.eclipse.jgit.util.IntList;
import org.eclipse.jgit.util.NB;

class ChunkWriter {
	private final byte chunkType;
	private final List<Entry> entries = new ArrayList<>();
	private final int blockSize;

	private int bytesInKeyTable;

	ChunkWriter(byte type, int bs) {
		chunkType = type;
		blockSize = bs;
	}

	byte blockType() {
		return chunkType;
	}

	byte[] lastKey() {
		return entries.get(entries.size() - 1).key;
	}

	int entryCount() {
		return entries.size();
	}

	int currentSize() {
		return computeBlockSize(0);
	}

	void addFirst(Entry entry) throws BlockSizeTooSmallException {
		if (!tryAdd(entry)) {
			// Insanely long names need a larger block size.
			throw blockSizeTooSmall(entry);
		}
	}

	boolean tryAdd(Entry entry) {
		byte[] key = entry.key;
		int prefixLen = 0;
		boolean first = entries.isEmpty();
		if (!first) {
			byte[] prior = entries.get(entries.size() - 1).key;
			prefixLen = commonPrefix(prior, prior.length, key);
		}

		int entrySize = entry.size(first, prefixLen);
		if (computeBlockSize(entrySize) > blockSize) {
			return false;
		}

		bytesInKeyTable += entrySize;
		entries.add(entry);
		return true;
	}

	private int computeBlockSize(int key) {
		int sz = bytesInKeyTable + key;
		return 1 + computeVarintSize(sz) + sz;
	}

	void writeTo(ReftableOutputStream os) throws IOException {
		byte[] prior = null;
		os.beginBlock(chunkType);
		os.writeVarint(bytesInKeyTable);
		for (int entryIdx = 0; entryIdx < entries.size(); entryIdx++) {
			Entry entry = entries.get(entryIdx);
			entry.writeKey(os, prior);
			entry.writeValue(os);
			prior = entry.key;
		}
		os.flushBlock();
	}

	private BlockSizeTooSmallException blockSizeTooSmall(Entry entry) {
		// Compute size required to fit this entry by itself.
		int min = computeBlockSize(entry.size(true, 0));
		return new BlockSizeTooSmallException(min);
	}

	static int commonPrefix(byte[] a, int n, byte[] b) {
		int len = Math.min(n, Math.min(a.length, b.length));
		for (int i = 0; i < len; i++) {
			if (a[i] != b[i]) {
				return i;
			}
		}
		return len;
	}

	static int encodeSuffixAndType(int sfx, int valueType) {
		return (sfx << 3) | valueType;
	}

	static int compare(
			byte[] a, int ai, int aLen,
			byte[] b, int bi, int bLen) {
		int aEnd = ai + aLen;
		int bEnd = bi + bLen;
		while (ai < aEnd && bi < bEnd) {
			int c = (a[ai++] & 0xff) - (b[bi++] & 0xff);
			if (c != 0) {
				return c;
			}
		}
		return aLen - bLen;
	}

	static abstract class Entry {
		static int compare(Entry ea, Entry eb) {
			byte[] a = ea.key;
			byte[] b = eb.key;
			return ChunkWriter.compare(a, 0, a.length, b, 0, b.length);
		}

		final byte[] key;

		Entry(byte[] key) {
			this.key = key;
		}

		void writeKey(ReftableOutputStream os, byte[] prior) {
			if (prior == null) {
				os.writeVarint(key.length);
				os.write(key, 0, key.length);
			} else {
				int pfx = commonPrefix(prior, prior.length, key);
				int sfx = key.length - pfx;
				os.writeVarint(pfx);
				os.writeVarint(sfx);
				os.write(key, pfx, sfx);
			}
		}

		int size(boolean first, int prefixLen) {
			int sfx = key.length - prefixLen;
			return (first ? 0 : computeVarintSize(prefixLen))
					+ computeVarintSize(sfx)
					+ sfx
					+ valueSize();
		}

		abstract byte blockType();
		abstract int valueType();
		abstract int valueSize();
		abstract void writeValue(ReftableOutputStream os) throws IOException;
	}

	static class IndexEntry extends Entry {
		private final long childAddr;

		IndexEntry(byte[] key, long childAddr) {
			super(key);
			this.childAddr = childAddr;
		}

		@Override
		byte blockType() {
			return INDEX_BLOCK_TYPE;
		}

		@Override
		int valueType() {
			return 0;
		}

		@Override
		int valueSize() {
			return computeVarintSize(childAddr);
		}

		@Override
		void writeValue(ReftableOutputStream os) {
			os.writeVarint(childAddr);
		}

		IndexEntry forIndexAt(long indexAddr) {
			if (indexAddr <= childAddr) {
				throw new IllegalArgumentException();
			}
			return new IndexEntry(key, indexAddr - childAddr);
		}
	}

	static class RefEntry extends Entry {
		final Ref ref;

		RefEntry(Ref ref) {
			super(nameUtf8(ref));
			this.ref = ref;
		}

		@Override
		byte blockType() {
			return REF_BLOCK_TYPE;
		}

		@Override
		int valueType() {
			if (ref.isSymbolic()) {
				return VALUE_TEXT;
			} else if (ref.getStorage() == NEW && ref.getObjectId() == null) {
				return VALUE_NONE;
			} else if (ref.getPeeledObjectId() != null) {
				return VALUE_2ID;
			} else {
				return VALUE_1ID;
			}
		}

		@Override
		int valueSize() {
			if (ref.isSymbolic()) {
				int nameLen = 5 + nameUtf8(ref.getTarget()).length;
				return 1 + computeVarintSize(nameLen) + nameLen;
			} else if (ref.getStorage() == NEW && ref.getObjectId() == null) {
				return 1;
			} else if (ref.getPeeledObjectId() != null) {
				return 1 + 2 * OBJECT_ID_LENGTH;
			} else {
				return 1 + OBJECT_ID_LENGTH;
			}
		}

		@Override
		void writeValue(ReftableOutputStream os) throws IOException {
			os.write(valueType());

			if (ref.isSymbolic()) {
				String target = ref.getTarget().getName();
				os.writeVarintString("ref: " + target); //$NON-NLS-1$
				return;
			}

			ObjectId id1 = ref.getObjectId();
			if (id1 == null) {
				if (ref.getStorage() == NEW) {
					return;
				}
				throw new IOException(JGitText.get().invalidId0);
			} else if (!ref.isPeeled()) {
				throw new IOException(JGitText.get().peeledRefIsRequired);
			}
			os.writeId(id1);

			ObjectId id2 = ref.getPeeledObjectId();
			if (id2 != null) {
				os.writeId(id2);
			}
		}

		private static byte[] nameUtf8(Ref ref) {
			return ref.getName().getBytes(UTF_8);
		}
	}

	static class TextEntry extends Entry {
		final byte[] value;

		TextEntry(String name, String value) {
			super(name.getBytes(UTF_8));
			this.value = value.getBytes(UTF_8);
		}

		@Override
		byte blockType() {
			return REF_BLOCK_TYPE;
		}

		@Override
		int valueType() {
			return VALUE_TEXT;
		}

		@Override
		int valueSize() {
			return 1 + computeVarintSize(value.length) + value.length;
		}

		@Override
		void writeValue(ReftableOutputStream os) throws IOException {
			os.write(valueType());
			os.writeVarint(value.length);
			os.write(value);
		}
	}

	static class ObjEntry extends Entry {
		final IntList blocks;

		ObjEntry(int idLen, ObjectId id, IntList blocks) {
			super(key(idLen, id));
			this.blocks = blocks;
		}

		private static byte[] key(int idLen, ObjectId id) {
			byte[] key = new byte[OBJECT_ID_LENGTH];
			id.copyRawTo(key, 0);
			if (idLen < OBJECT_ID_LENGTH) {
				return Arrays.copyOf(key, idLen);
			}
			return key;
		}

		@Override
		byte blockType() {
			return OBJ_BLOCK_TYPE;
		}

		@Override
		int valueType() {
			int cnt = blocks.size();
			return cnt > VALUE_TYPE_MASK ? 0 : cnt;
		}

		@Override
		int valueSize() {
			int n = 0;
			int cnt = blocks.size();
			if (cnt > VALUE_TYPE_MASK) {
				n += computeVarintSize(cnt);
			}
			n += computeVarintSize(blocks.get(0));
			for (int j = 1; j < cnt; j++) {
				int prior = blocks.get(j - 1);
				int b = blocks.get(j);
				n += computeVarintSize(b - prior);
			}
			return n;
		}

		@Override
		void writeValue(ReftableOutputStream os) throws IOException {
			int cnt = blocks.size();
			if (cnt > VALUE_TYPE_MASK) {
				os.writeVarint(cnt);
			}
			os.writeVarint(blocks.get(0));
			for (int j = 1; j < cnt; j++) {
				int prior = blocks.get(j - 1);
				int b = blocks.get(j);
				os.writeVarint(b - prior);
			}
		}
	}

	static class LogEntry extends Entry {
		final ObjectId oldId;
		final ObjectId newId;
		final long timeSecs;
		final short tz;
		final byte[] name;
		final byte[] email;
		final byte[] msg;

		LogEntry(String refName, long updateIndex, PersonIdent who,
				ObjectId oldId, ObjectId newId, String message) {
			super(key(refName, updateIndex));

			this.oldId = oldId;
			this.newId = newId;
			this.timeSecs = who.getWhen().getTime() / 1000L;
			this.tz = (short) who.getTimeZoneOffset();
			this.name = who.getName().getBytes(UTF_8);
			this.email = who.getEmailAddress().getBytes(UTF_8);
			this.msg = message.getBytes(UTF_8);
		}

		static byte[] key(String ref, long index) {
			byte[] name = ref.getBytes(UTF_8);
			byte[] key = Arrays.copyOf(name, name.length + 1 + 8);
			NB.encodeInt64(key, key.length - 8, reverseUpdateIndex(index));
			return key;
		}

		@Override
		byte blockType() {
			return LOG_BLOCK_TYPE;
		}

		@Override
		int valueType() {
			return VALUE_LOG_RECORD;
		}

		@Override
		int valueSize() {
			return 2 * OBJECT_ID_LENGTH
					+ computeVarintSize(timeSecs)
					+ 2 // tz
					+ computeVarintSize(name.length) + name.length
					+ computeVarintSize(email.length) + email.length
					+ computeVarintSize(msg.length) + msg.length;
		}

		@Override
		void writeValue(ReftableOutputStream os) {
			os.writeId(oldId);
			os.writeId(newId);
			os.writeVarint(timeSecs);
			os.writeInt16(tz);
			os.writeVarintString(name);
			os.writeVarintString(email);
			os.writeVarintString(msg);
		}
	}
}