/*
    * Copyright (C) 2010, 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.pack;
  
  import java.io.EOFException;
  import java.io.IOException;
  import java.io.OutputStream;
  import java.util.zip.Deflater;
  
  import org.eclipse.jgit.errors.IncorrectObjectTypeException;
  import org.eclipse.jgit.errors.LargeObjectException;
  import org.eclipse.jgit.errors.MissingObjectException;
  import org.eclipse.jgit.lib.ObjectReader;
  import org.eclipse.jgit.lib.ProgressMonitor;
  import org.eclipse.jgit.storage.pack.PackConfig;
  import org.eclipse.jgit.util.TemporaryBuffer;
  
  final class DeltaWindow {
  	private static final boolean NEXT_RES = false;
  	private static final boolean NEXT_SRC = true;
  
  	private final PackConfig config;
  	private final DeltaCache deltaCache;
  	private final ObjectReader reader;
  	private final ProgressMonitor monitor;
  	private final long bytesPerUnit;
  	private long bytesProcessed;
  
  	/** Maximum number of bytes to admit to the window at once. */
  	private final long maxMemory;
  
  	/** Maximum depth we should create for any delta chain. */
  	private final int maxDepth;
  
  	private final ObjectToPack[] toSearch;
  	private int cur;
  	private int end;
  
  	/** Amount of memory we have loaded right now. */
  	private long loaded;
  
  	// The object we are currently considering needs a lot of state:
  
  	/** Window entry of the object we are currently considering. */
  	private DeltaWindowEntry res;
  
  	/** If we have chosen a base, the window entry it was created from. */
  	private DeltaWindowEntry bestBase;
  	private int deltaLen;
  	private Object deltaBuf;
  
  	/** Used to compress cached deltas. */
  	private Deflater deflater;
  
  	DeltaWindow(PackConfig pc, DeltaCache dc, ObjectReader or,
  			ProgressMonitor pm, long bpu,
  			ObjectToPack[] in, int beginIndex, int endIndex) {
  		config = pc;
 		deltaCache = dc;
 		reader = or;
 		monitor = pm;
 		bytesPerUnit = bpu;
 		toSearch = in;
 		cur = beginIndex;
 		end = endIndex;
 
 		maxMemory = Math.max(0, config.getDeltaSearchMemoryLimit());
 		maxDepth = config.getMaxDeltaDepth();
 		res = DeltaWindowEntry.createWindow(config.getDeltaSearchWindowSize());
 	}
 
 	synchronized DeltaTask.Slice remaining() {
 		int e = end;
 		int halfRemaining = (e - cur) >>> 1;
 		if (0 == halfRemaining)
 			return null;
 
 		int split = e - halfRemaining;
 		int h = toSearch[split].getPathHash();
 
 		// Attempt to split on the next path after the 50% split point.
 		for (int n = split + 1; n < e; n++) {
 			if (h != toSearch[n].getPathHash())
 				return new DeltaTask.Slice(n, e);
 		}
 
 		if (h != toSearch[cur].getPathHash()) {
 			// Try to split on the path before the 50% split point.
 			// Do not split the path currently being processed.
 			for (int p = split - 1; cur < p; p--) {
 				if (h != toSearch[p].getPathHash())
 					return new DeltaTask.Slice(p + 1, e);
 			}
 		}
 		return null;
 	}
 
 	synchronized boolean tryStealWork(DeltaTask.Slice s) {
 		if (s.beginIndex <= cur || end <= s.beginIndex)
 			return false;
 		end = s.beginIndex;
 		return true;
 	}
 
 	void search() throws IOException {
 		try {
 			for (;;) {
 				ObjectToPack next;
 				synchronized (this) {
 					if (end <= cur)
 						break;
 					next = toSearch[cur++];
 				}
 				if (maxMemory != 0) {
 					clear(res);
 					final long need = estimateSize(next);
 					DeltaWindowEntry n = res.next;
 					for (; maxMemory < loaded + need && n != res; n = n.next)
 						clear(n);
 				}
 				res.set(next);
 				clearWindowOnTypeSwitch();
 
 				if (res.object.isEdge() || res.object.doNotAttemptDelta()) {
 					// We don't actually want to make a delta for
 					// them, just need to push them into the window
 					// so they can be read by other objects.
 					keepInWindow();
 				} else {
 					// Search for a delta for the current window slot.
 					if (bytesPerUnit <= (bytesProcessed += next.getWeight())) {
 						int d = (int) (bytesProcessed / bytesPerUnit);
 						monitor.update(d);
 						bytesProcessed -= d * bytesPerUnit;
 					}
 					searchInWindow();
 				}
 			}
 		} finally {
 			if (deflater != null)
 				deflater.end();
 		}
 	}
 
 	private static long estimateSize(ObjectToPack ent) {
 		return DeltaIndex.estimateIndexSize(ent.getWeight());
 	}
 
 	private static long estimateIndexSize(DeltaWindowEntry ent) {
 		if (ent.buffer == null)
 			return estimateSize(ent.object);
 
 		int len = ent.buffer.length;
 		return DeltaIndex.estimateIndexSize(len) - len;
 	}
 
 	private void clearWindowOnTypeSwitch() {
 		DeltaWindowEntry p = res.prev;
 		if (!p.empty() && res.type() != p.type()) {
 			for (; p != res; p = p.prev) {
 				clear(p);
 			}
 		}
 	}
 
 	private void clear(DeltaWindowEntry ent) {
 		if (ent.index != null)
 			loaded -= ent.index.getIndexSize();
 		else if (ent.buffer != null)
 			loaded -= ent.buffer.length;
 		ent.set(null);
 	}
 
 	private void searchInWindow() throws IOException {
 		// Loop through the window backwards, considering every entry.
 		// This lets us look at the bigger objects that came before.
 		for (DeltaWindowEntry src = res.prev; src != res; src = src.prev) {
 			if (src.empty())
 				break;
 			if (delta(src) /* == NEXT_SRC */)
 				continue;
 			bestBase = null;
 			deltaBuf = null;
 			return;
 		}
 
 		// We couldn't find a suitable delta for this object, but it may
 		// still be able to act as a base for another one.
 		if (bestBase == null) {
 			keepInWindow();
 			return;
 		}
 
 		// Select this best matching delta as the base for the object.
 		//
 		ObjectToPack srcObj = bestBase.object;
 		ObjectToPack resObj = res.object;
 		if (srcObj.isEdge()) {
 			// The source (the delta base) is an edge object outside of the
 			// pack. Its part of the common base set that the peer already
 			// has on hand, so we don't want to send it. We have to store
 			// an ObjectId and *NOT* an ObjectToPack for the base to ensure
 			// the base isn't included in the outgoing pack file.
 			resObj.setDeltaBase(srcObj.copy());
 		} else {
 			// The base is part of the pack we are sending, so it should be
 			// a direct pointer to the base.
 			resObj.setDeltaBase(srcObj);
 		}
 
 		int depth = srcObj.getDeltaDepth() + 1;
 		resObj.setDeltaDepth(depth);
 		resObj.clearReuseAsIs();
 		cacheDelta(srcObj, resObj);
 
 		if (depth < maxDepth) {
 			// Reorder the window so that the best base will be tested
 			// first for the next object, and the current object will
 			// be the second candidate to consider before any others.
 			res.makeNext(bestBase);
 			res = bestBase.next;
 		}
 
 		bestBase = null;
 		deltaBuf = null;
 	}
 
 	private boolean delta(DeltaWindowEntry src)
 			throws IOException {
 		// If the sizes are radically different, this is a bad pairing.
 		if (res.size() < src.size() >>> 4)
 			return NEXT_SRC;
 
 		int msz = deltaSizeLimit(src);
 		if (msz <= 8) // Nearly impossible to fit useful delta.
 			return NEXT_SRC;
 
 		// If we have to insert a lot to make this work, find another.
 		if (res.size() - src.size() > msz)
 			return NEXT_SRC;
 
 		DeltaIndex srcIndex;
 		try {
 			srcIndex = index(src);
 		} catch (LargeObjectException tooBig) {
 			// If the source is too big to work on, skip it.
 			return NEXT_SRC;
 		} catch (IOException notAvailable) {
 			if (src.object.isEdge()) // Missing edges are OK.
 				return NEXT_SRC;
 			throw notAvailable;
 		}
 
 		byte[] resBuf;
 		try {
 			resBuf = buffer(res);
 		} catch (LargeObjectException tooBig) {
 			// If its too big, move on to another item.
 			return NEXT_RES;
 		}
 
 		try {
 			OutputStream delta = msz <= (8 << 10)
 				? new ArrayStream(msz)
 				: new TemporaryBuffer.Heap(msz);
 			if (srcIndex.encode(delta, resBuf, msz))
 				selectDeltaBase(src, delta);
 		} catch (IOException deltaTooBig) {
 			// Unlikely, encoder should see limit and return false.
 		}
 		return NEXT_SRC;
 	}
 
 	private void selectDeltaBase(DeltaWindowEntry src, OutputStream delta) {
 		bestBase = src;
 
 		if (delta instanceof ArrayStream) {
 			ArrayStream a = (ArrayStream) delta;
 			deltaBuf = a.buf;
 			deltaLen = a.cnt;
 		} else {
 			TemporaryBuffer.Heap b = (TemporaryBuffer.Heap) delta;
 			deltaBuf = b;
 			deltaLen = (int) b.length();
 		}
 	}
 
 	private int deltaSizeLimit(DeltaWindowEntry src) {
 		if (bestBase == null) {
 			// Any delta should be no more than 50% of the original size
 			// (for text files deflate of whole form should shrink 50%).
 			int n = res.size() >>> 1;
 
 			// Evenly distribute delta size limits over allowed depth.
 			// If src is non-delta (depth = 0), delta <= 50% of original.
 			// If src is almost at limit (9/10), delta <= 10% of original.
 			return n * (maxDepth - src.depth()) / maxDepth;
 		}
 
 		// With a delta base chosen any new delta must be "better".
 		// Retain the distribution described above.
 		int d = bestBase.depth();
 		int n = deltaLen;
 
 		// If src is whole (depth=0) and base is near limit (depth=9/10)
 		// any delta using src can be 10x larger and still be better.
 		//
 		// If src is near limit (depth=9/10) and base is whole (depth=0)
 		// a new delta dependent on src must be 1/10th the size.
 		return n * (maxDepth - src.depth()) / (maxDepth - d);
 	}
 
 	private void cacheDelta(ObjectToPack srcObj, ObjectToPack resObj) {
 		if (deltaCache.canCache(deltaLen, srcObj, resObj)) {
 			try {
 				byte[] zbuf = new byte[deflateBound(deltaLen)];
 				ZipStream zs = new ZipStream(deflater(), zbuf);
 				if (deltaBuf instanceof byte[])
 					zs.write((byte[]) deltaBuf, 0, deltaLen);
 				else
 					((TemporaryBuffer.Heap) deltaBuf).writeTo(zs, null);
 				deltaBuf = null;
 				int len = zs.finish();
 
 				resObj.setCachedDelta(deltaCache.cache(zbuf, len, deltaLen));
 				resObj.setCachedSize(deltaLen);
 			} catch (IOException err) {
 				deltaCache.credit(deltaLen);
 			} catch (OutOfMemoryError err) {
 				deltaCache.credit(deltaLen);
 			}
 		}
 	}
 
 	private static int deflateBound(int insz) {
 		return insz + ((insz + 7) >> 3) + ((insz + 63) >> 6) + 11;
 	}
 
 	private void keepInWindow() {
 		res = res.next;
 	}
 
 	private DeltaIndex index(DeltaWindowEntry ent)
 			throws MissingObjectException, IncorrectObjectTypeException,
 			IOException, LargeObjectException {
 		DeltaIndex idx = ent.index;
 		if (idx == null) {
 			checkLoadable(ent, estimateIndexSize(ent));
 
 			try {
 				idx = new DeltaIndex(buffer(ent));
 			} catch (OutOfMemoryError noMemory) {
 				LargeObjectException.OutOfMemory e;
 				e = new LargeObjectException.OutOfMemory(noMemory);
 				e.setObjectId(ent.object);
 				throw e;
 			}
 			if (maxMemory != 0)
 				loaded += idx.getIndexSize() - idx.getSourceSize();
 			ent.index = idx;
 		}
 		return idx;
 	}
 
 	private byte[] buffer(DeltaWindowEntry ent) throws MissingObjectException,
 			IncorrectObjectTypeException, IOException, LargeObjectException {
 		byte[] buf = ent.buffer;
 		if (buf == null) {
 			checkLoadable(ent, ent.size());
 
 			buf = PackWriter.buffer(config, reader, ent.object);
 			if (maxMemory != 0)
 				loaded += buf.length;
 			ent.buffer = buf;
 		}
 		return buf;
 	}
 
 	private void checkLoadable(DeltaWindowEntry ent, long need) {
 		if (maxMemory == 0)
 			return;
 
 		DeltaWindowEntry n = res.next;
 		for (; maxMemory < loaded + need; n = n.next) {
 			clear(n);
 			if (n == ent)
 				throw new LargeObjectException.ExceedsLimit(
 						maxMemory, loaded + need);
 		}
 	}
 
 	private Deflater deflater() {
 		if (deflater == null)
 			deflater = new Deflater(config.getCompressionLevel());
 		else
 			deflater.reset();
 		return deflater;
 	}
 
 	static final class ZipStream extends OutputStream {
 		private final Deflater deflater;
 
 		private final byte[] zbuf;
 
 		private int outPtr;
 
 		ZipStream(Deflater deflater, byte[] zbuf) {
 			this.deflater = deflater;
 			this.zbuf = zbuf;
 		}
 
 		int finish() throws IOException {
 			deflater.finish();
 			for (;;) {
 				if (outPtr == zbuf.length)
 					throw new EOFException();
 
 				int n = deflater.deflate(zbuf, outPtr, zbuf.length - outPtr);
 				if (n == 0) {
 					if (deflater.finished())
 						return outPtr;
 					throw new IOException();
 				}
 				outPtr += n;
 			}
 		}
 
 		@Override
 		public void write(byte[] b, int off, int len) throws IOException {
 			deflater.setInput(b, off, len);
 			for (;;) {
 				if (outPtr == zbuf.length)
 					throw new EOFException();
 
 				int n = deflater.deflate(zbuf, outPtr, zbuf.length - outPtr);
 				if (n == 0) {
 					if (deflater.needsInput())
 						break;
 					throw new IOException();
 				}
 				outPtr += n;
 			}
 		}
 
 		@Override
 		public void write(int b) throws IOException {
 			throw new UnsupportedOperationException();
 		}
 	}
 
 	static final class ArrayStream extends OutputStream {
 		final byte[] buf;
 		int cnt;
 
 		ArrayStream(int max) {
 			buf = new byte[max];
 		}
 
 		@Override
 		public void write(int b) throws IOException {
 			if (cnt == buf.length)
 				throw new IOException();
 			buf[cnt++] = (byte) b;
 		}
 
 		@Override
 		public void write(byte[] b, int off, int len) throws IOException {
 			if (len > buf.length - cnt)
 				throw new IOException();
 			System.arraycopy(b, off, buf, cnt, len);
 			cnt += len;
 		}
 	}
 }