ReversedLinesFileReader.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* https://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.io.input;
import java.io.Closeable;
import java.io.File;
import java.io.IOException;
import java.io.UnsupportedEncodingException;
import java.nio.ByteBuffer;
import java.nio.channels.SeekableByteChannel;
import java.nio.charset.Charset;
import java.nio.charset.CharsetEncoder;
import java.nio.charset.StandardCharsets;
import java.nio.file.Path;
import java.nio.file.StandardOpenOption;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import org.apache.commons.io.Charsets;
import org.apache.commons.io.FileSystem;
import org.apache.commons.io.StandardLineSeparator;
import org.apache.commons.io.build.AbstractStreamBuilder;
import org.apache.commons.io.function.IOIterable;
import org.apache.commons.io.function.IOIterator;
/**
* Reads lines in a file reversely (similar to a BufferedReader, but starting at the last line). Useful for e.g. searching in log files.
* <p>
* To build an instance, use {@link Builder}.
* </p>
* <p>
* For example:
* </p>
* <pre>
* <code>
* try (ReversedLinesFileReader reader = ReversedLinesFileReader.builder()
* .setPath(path)
* .setBufferSize(4096)
* .setCharset(StandardCharsets.UTF_8)
* .get()) {
* reader.forEach(line -> System.out.println(line));
* }
* </code>
* </pre>
*
* @see Builder
* @since 2.2
*/
public class ReversedLinesFileReader implements Closeable, IOIterable<String> {
// @formatter:off
/**
* Builds a new {@link ReversedLinesFileReader}.
*
* <p>
* For example:
* </p>
* <pre>{@code
* ReversedLinesFileReader reader = ReversedLinesFileReader.builder()
* .setPath(path)
* .setBufferSize(4096)
* .setCharset(StandardCharsets.UTF_8)
* .get());}
* </pre>
*
* @see #get()
* @since 2.12.0
*/
// @formatter:on
public static class Builder extends AbstractStreamBuilder<ReversedLinesFileReader, Builder> {
/**
* Constructs a new builder of {@link ReversedLinesFileReader}.
*/
public Builder() {
setBufferSizeDefault(DEFAULT_BLOCK_SIZE);
setBufferSize(DEFAULT_BLOCK_SIZE);
setOpenOptions(StandardOpenOption.READ);
}
/**
* Builds a new {@link ReversedLinesFileReader}.
* <p>
* You must set an aspect that supports {@link #getInputStream()} on this builder, otherwise, this method throws an exception.
* </p>
* <p>
* This builder uses the following aspects:
* </p>
* <ul>
* <li>{@link #getPath()} gets the target aspect.</li>
* <li>{@link #getBufferSize()}</li>
* <li>{@link #getCharset()}</li>
* </ul>
*
* @return A new instance.
* @throws IllegalStateException if the {@code origin} is {@code null}.
* @throws UnsupportedOperationException if the origin cannot be converted to a {@link Path}.
* @throws IOException if an I/O error occurs converting to a {@link Path} using {@link #getPath()}.
* @see #getPath()
* @see #getBufferSize()
* @see #getCharset()
* @see #getUnchecked()
*/
@Override
public ReversedLinesFileReader get() throws IOException {
return new ReversedLinesFileReader(this);
}
}
private final class FilePart {
private final long partNumber;
/**
* This block's bytes, plus a small "bridge" of up to {@code avoidNewlineSplitBufferSize} bytes copied from the head of {@link #tail} so newline
* sequences split across the block boundary can be matched.
*/
private final byte[] data;
/**
* The number of bytes in {@link #data} belonging to this block; the remainder is the bridge.
*/
private final int blockLength;
/**
* The accumulated remainder of the following (later-in-file) blocks, in file order, or null.
*
* <p>
* The prefix can contain deferred newline bytes that still need to be checked across a block boundary. The rest has already been scanned.
* These bytes virtually follow this block's bytes and are joined when a line is emitted, instead of being re-copied into every preceding block's
* buffer.
* </p>
*/
private final Deque<byte[]> tail;
/**
* The total number of bytes across the {@link #tail} segments.
*/
private final long tailLength;
/**
* The unemitted remainder of this part, as segments in file order, to hand to the preceding part; null if none.
*/
private Deque<byte[]> leftOver;
/**
* The total number of bytes across the {@link #leftOver} segments.
*/
private long leftOverLength;
/**
* Index of the last unemitted byte in the virtual buffer formed by {@code data[0..blockLength - 1]} followed by the {@link #tail} bytes.
*/
private long currentLastBytePos;
/**
* Constructs a new instance.
*
* @param partNumber The part number.
* @param length its length.
* @param tail remainder of the following file parts, as segments in file order, or null.
* @param tailLength The total number of bytes across the {@code tail} segments.
* @throws IOException Thrown if there is a problem reading the file.
*/
private FilePart(final long partNumber, final int length, final Deque<byte[]> tail, final long tailLength) throws IOException {
this.partNumber = partNumber;
this.blockLength = length;
this.tail = tail;
this.tailLength = tailLength;
// Copy only a tiny bridge from the tail's head; the rest of the tail is never re-copied per block.
final int bridgeLength = (int) Math.min(tailLength, avoidNewlineSplitBufferSize);
this.data = new byte[length + bridgeLength];
final long off = (partNumber - 1) * blockSize;
// read data
if (partNumber > 0 /* file not empty */) {
channel.position(off);
final int countRead = channel.read(ByteBuffer.wrap(data, 0, length));
if (countRead != length) {
throw new IllegalStateException("Count of requested bytes and actually read bytes don't match");
}
}
// copy the bridge bytes from the head of the tail segments into data arr
int bridgePos = length;
int bridgeRemaining = bridgeLength;
if (bridgeRemaining > 0) {
for (final byte[] segment : tail) {
final int n = Math.min(segment.length, bridgeRemaining);
System.arraycopy(segment, 0, data, bridgePos, n);
bridgePos += n;
bridgeRemaining -= n;
if (bridgeRemaining == 0) {
break;
}
}
}
this.currentLastBytePos = length + tailLength - 1;
this.leftOver = null;
}
/**
* Copies an inclusive range of the virtual buffer ({@code data[0..blockLength - 1]} followed by the {@link #tail} bytes) into a new array.
*
* @param from Start index in the virtual buffer, inclusive.
* @param toInclusive End index in the virtual buffer, inclusive.
* @return A new byte array holding the requested range.
*/
private byte[] copyVirtual(final long from, final long toInclusive) {
final long count = toInclusive - from + 1;
if (count > MAX_LINE_BYTES) {
throw new IllegalStateException("Line too long: " + count + " bytes exceed the maximum array size");
}
final byte[] result = new byte[(int) count];
int resultPos = 0;
if (from < blockLength) {
final int n = (int) (Math.min(toInclusive + 1, blockLength) - from);
System.arraycopy(data, (int) from, result, 0, n);
resultPos = n;
}
if (toInclusive >= blockLength && tail != null) {
long skip = Math.max(0, from - blockLength);
long remaining = toInclusive - blockLength + 1 - skip;
for (final byte[] segment : tail) {
if (skip >= segment.length) {
skip -= segment.length;
continue;
}
final int n = (int) Math.min(segment.length - skip, remaining);
System.arraycopy(segment, (int) skip, result, resultPos, n);
resultPos += n;
remaining -= n;
skip = 0;
if (remaining == 0) {
break;
}
}
}
return result;
}
/**
* Records the unemitted remainder of this part, as segments, for the preceding part.
*/
private void createLeftOver() {
if (currentLastBytePos >= data.length) {
// Nothing was emitted from this part: keep the accumulated tail segments as-is and prepend this block's
// bytes - O(blockSize) work instead of re-copying the whole accumulated remainder.
leftOver = tail;
leftOver.addFirst(Arrays.copyOf(data, blockLength));
leftOverLength = blockLength + tailLength;
} else if (currentLastBytePos > -1) {
// The remainder lies entirely within data (this block plus at most the bridge bytes).
leftOver = new ArrayDeque<>();
leftOver.add(copyVirtual(0, currentLastBytePos));
leftOverLength = currentLastBytePos + 1;
} else {
leftOver = null;
leftOverLength = 0;
}
currentLastBytePos = -1;
}
/**
* Finds the new-line sequence and return its length.
*
* @param data buffer to scan.
* @param i start offset in buffer.
* @return length of newline sequence or 0 if none found.
*/
private int getNewLineMatchByteCount(final byte[] data, final int i) {
for (final byte[] newLineSequence : newLineSequences) {
boolean match = true;
for (int j = newLineSequence.length - 1; j >= 0; j--) {
final int k = i + j - (newLineSequence.length - 1);
match &= k >= 0 && data[k] == newLineSequence[j];
}
if (match) {
return newLineSequence.length;
}
}
return 0;
}
/**
* Joins the leftOver segments into a single array.
*
* @return A new byte array holding the leftOver bytes.
*/
private byte[] joinLeftOver() {
if (leftOverLength > MAX_LINE_BYTES) {
throw new IllegalStateException("Line too long: " + leftOverLength + " bytes exceed the maximum array size");
}
final byte[] result = new byte[(int) leftOverLength];
int resultPos = 0;
for (final byte[] segment : leftOver) {
System.arraycopy(segment, 0, result, resultPos, segment.length);
resultPos += segment.length;
}
return result;
}
/**
* Reads a line.
*
* @return The line or null.
*/
private String readLine() { //NOPMD Bug in PMD
String line = null;
int newLineMatchByteCount;
final boolean isLastFilePart = partNumber == 1;
long i = currentLastBytePos;
if (i >= data.length) {
// Bytes deeper in the tail were already scanned and found newline-free by the file parts that
// produced them; skip whole byteDecrement steps so the scan stays on the original cursor positions.
i -= (i - data.length + byteDecrement) / byteDecrement * byteDecrement;
}
if (currentLastBytePos == -1 && isLastFilePart && leftOver != null) {
line = new String(joinLeftOver(), charset);
leftOver = null;
return line;
}
while (i > -1) {
if (!isLastFilePart && i < avoidNewlineSplitBufferSize) {
// avoidNewlineSplitBuffer: for all except the last file part we
// take a few bytes to the next file part to avoid splitting of newlines
createLeftOver();
break; // skip last few bytes and leave it to the next file part
}
// check for newline
if ((newLineMatchByteCount = getNewLineMatchByteCount(data, (int) i)) > 0 /* found newline */) {
final long lineStart = i + 1;
final long lineLengthBytes = currentLastBytePos - lineStart + 1;
if (lineLengthBytes < 0) {
throw new IllegalStateException("Unexpected negative line length=" + lineLengthBytes);
}
line = new String(copyVirtual(lineStart, currentLastBytePos), charset);
currentLastBytePos = i - newLineMatchByteCount;
if (isLastFilePart && currentLastBytePos == -1 && i == 0) {
leftOver = new ArrayDeque<>();
leftOverLength = 0;
}
break; // found line
}
// move cursor
i -= byteDecrement;
// end of file part handling
if (i < 0) {
if (isLastFilePart) {
final long lineLengthBytes = currentLastBytePos + 1;
if (lineLengthBytes > 0) {
line = new String(copyVirtual(0, currentLastBytePos), charset);
}
currentLastBytePos = -1;
} else {
createLeftOver();
}
break; // end of file part
}
}
// there will be partNumber line break anymore, this is the first line of the file
if (line == null && isLastFilePart && leftOver != null) {
line = new String(joinLeftOver(), charset);
leftOver = null;
}
return line;
}
/**
* Handles block rollover
*
* @return The new FilePart or null.
* @throws IOException Thrown if there was a problem reading the file.
*/
private FilePart rollOver() throws IOException {
if (currentLastBytePos > -1) {
throw new IllegalStateException("Current currentLastCharPos unexpectedly positive... "
+ "last readLine() should have returned something! currentLastCharPos=" + currentLastBytePos);
}
if (partNumber > 1) {
return new FilePart(partNumber - 1, blockSize, leftOver, leftOverLength);
}
// NO 1 was the last FilePart, we're finished
if (leftOver != null) {
throw new IllegalStateException("Unexpected leftover of the last block: leftOverOfThisFilePart="
+ new String(joinLeftOver(), charset));
}
return null;
}
}
private static final String EMPTY_STRING = "";
private static final int DEFAULT_BLOCK_SIZE = FileSystem.getCurrent().getBlockSize();
/**
* A conservative maximum byte array size.
*/
private static final long MAX_LINE_BYTES = Integer.MAX_VALUE - 8;
/**
* Constructs a new {@link Builder}.
*
* @return A new {@link Builder}.
* @since 2.12.0
*/
public static Builder builder() {
return new Builder();
}
private final int blockSize;
private final Charset charset;
private final SeekableByteChannel channel;
private final long totalByteLength;
private final long totalBlockCount;
private final byte[][] newLineSequences;
private final int avoidNewlineSplitBufferSize;
private final int byteDecrement;
private FilePart currentFilePart;
private boolean trailingNewlineOfFileSkipped;
private ReversedLinesFileReader(final Builder builder) throws IOException {
this.blockSize = builder.getBufferSize();
this.charset = Charsets.toCharset(builder.getCharset());
// check & prepare encoding
final CharsetEncoder charsetEncoder = charset.newEncoder();
final float maxBytesPerChar = charsetEncoder.maxBytesPerChar();
if (maxBytesPerChar == 1f || charset == StandardCharsets.UTF_8) {
// all one byte encodings are partNumber problem
byteDecrement = 1;
} else if (charset == Charset.forName("Shift_JIS") || // Same as for UTF-8
// http://www.herongyang.com/Unicode/JIS-Shift-JIS-Encoding.html
charset == Charset.forName("windows-31j") || // Windows code page 932 (Japanese)
charset == Charset.forName("x-windows-949") || // Windows code page 949 (Korean)
charset == Charset.forName("gbk") || // Windows code page 936 (Simplified Chinese)
charset == Charset.forName("x-windows-950")) { // Windows code page 950 (Traditional Chinese)
byteDecrement = 1;
} else if (charset == StandardCharsets.UTF_16BE || charset == StandardCharsets.UTF_16LE) {
// UTF-16 new line sequences are not allowed as second tuple of four byte
// sequences,
// however byte order has to be specified
byteDecrement = 2;
} else if (charset == StandardCharsets.UTF_16) {
throw new UnsupportedEncodingException("For UTF-16, you need to specify the byte order (use UTF-16BE or UTF-16LE)");
} else {
throw new UnsupportedEncodingException("Encoding " + charset + " is not supported yet (feel free to submit a patch)");
}
// NOTE: The new line sequences are matched in the order given, so it is
// important that \r\n is BEFORE \n
this.newLineSequences = new byte[][] { StandardLineSeparator.CRLF.getBytes(charset), StandardLineSeparator.LF.getBytes(charset),
StandardLineSeparator.CR.getBytes(charset) };
this.avoidNewlineSplitBufferSize = newLineSequences[0].length;
// Open file
this.channel = builder.getChannel(SeekableByteChannel.class);
this.totalByteLength = channel.size();
int lastBlockLength = (int) (totalByteLength % blockSize);
if (lastBlockLength > 0) {
this.totalBlockCount = totalByteLength / blockSize + 1;
} else {
this.totalBlockCount = totalByteLength / blockSize;
if (totalByteLength > 0) {
lastBlockLength = blockSize;
}
}
this.currentFilePart = new FilePart(totalBlockCount, lastBlockLength, null, 0);
}
/**
* Constructs a ReversedLinesFileReader with default block size of 4KB and the virtual machine's {@linkplain Charset#defaultCharset() default charset}.
*
* @param file The file to be read.
* @throws IOException Thrown if an I/O error occurs.
* @deprecated Use {@link #builder()}, {@link Builder}, and {@link Builder#get()}
*/
@Deprecated
public ReversedLinesFileReader(final File file) throws IOException {
this(file, DEFAULT_BLOCK_SIZE, Charset.defaultCharset());
}
/**
* Constructs a ReversedLinesFileReader with default block size of 4KB and the
* specified encoding.
*
* @param file The file to be read.
* @param charset The charset to use, null uses the default Charset.
* @throws IOException Thrown if an I/O error occurs.
* @since 2.5
* @deprecated Use {@link #builder()}, {@link Builder}, and {@link Builder#get()}
*/
@Deprecated
public ReversedLinesFileReader(final File file, final Charset charset) throws IOException {
this(file.toPath(), charset);
}
/**
* Constructs a ReversedLinesFileReader with the given block size and encoding.
*
* @param file The file to be read.
* @param blockSize size of the internal buffer (for ideal performance this
* should match with the block size of the underlying file
* system).
* @param charset The encoding of the file, null uses the default Charset.
* @throws IOException Thrown if an I/O error occurs.
* @since 2.3
* @deprecated Use {@link #builder()}, {@link Builder}, and {@link Builder#get()}
*/
@Deprecated
public ReversedLinesFileReader(final File file, final int blockSize, final Charset charset) throws IOException {
this(file.toPath(), blockSize, charset);
}
/**
* Constructs a ReversedLinesFileReader with the given block size and encoding.
*
* @param file The file to be read.
* @param blockSize size of the internal buffer (for ideal performance this
* should match with the block size of the underlying file
* system).
* @param charsetName The encoding of the file, null uses the default Charset.
* @throws IOException if an I/O error occurs.
* @throws java.nio.charset.UnsupportedCharsetException if the encoding is not supported.
* @deprecated Use {@link #builder()}, {@link Builder}, and {@link Builder#get()}
*/
@Deprecated
public ReversedLinesFileReader(final File file, final int blockSize, final String charsetName) throws IOException {
this(file.toPath(), blockSize, charsetName);
}
/**
* Constructs a ReversedLinesFileReader with default block size of 4KB and the
* specified encoding.
*
* @param file The file to be read.
* @param charset The charset to use, null uses the default Charset.
* @throws IOException Thrown if an I/O error occurs.
* @since 2.7
* @deprecated Use {@link #builder()}, {@link Builder}, and {@link Builder#get()}
*/
@Deprecated
public ReversedLinesFileReader(final Path file, final Charset charset) throws IOException {
this(file, DEFAULT_BLOCK_SIZE, charset);
}
/**
* Constructs a ReversedLinesFileReader with the given block size and encoding.
*
* @param file The file to be read.
* @param blockSize size of the internal buffer (for ideal performance this
* should match with the block size of the underlying file
* system).
* @param charset The encoding of the file, null uses the default Charset.
* @throws IOException Thrown if an I/O error occurs.
* @since 2.7
* @deprecated Use {@link #builder()}, {@link Builder}, and {@link Builder#get()}
*/
@Deprecated
public ReversedLinesFileReader(final Path file, final int blockSize, final Charset charset) throws IOException {
this(builder().setPath(file).setBufferSize(blockSize).setCharset(charset));
}
/**
* Constructs a ReversedLinesFileReader with the given block size and encoding.
*
* @param file The file to be read.
* @param blockSize size of the internal buffer (for ideal performance this
* should match with the block size of the underlying file
* system).
* @param charsetName The encoding of the file, null uses the default Charset.
* @throws IOException if an I/O error occurs.
* @throws java.nio.charset.UnsupportedCharsetException if the encoding is not supported.
* @since 2.7
* @deprecated Use {@link #builder()}, {@link Builder}, and {@link Builder#get()}
*/
@Deprecated
public ReversedLinesFileReader(final Path file, final int blockSize, final String charsetName) throws IOException {
this(file, blockSize, Charsets.toCharset(charsetName));
}
/**
* Closes underlying resources.
*
* @throws IOException Thrown if an I/O error occurs.
*/
@Override
public void close() throws IOException {
channel.close();
}
@Override
public IOIterator<String> iterator() {
return new IOIterator<String>() {
private String next;
@Override
public boolean hasNext() throws IOException {
if (next == null) {
next = readLine();
}
return next != null;
}
@Override
public String next() throws IOException {
if (next == null) {
next = readLine();
}
final String tmp = next;
next = null;
return tmp;
}
@Override
public Iterator<String> unwrap() {
return null;
}
};
}
/**
* Gets the next line of the file from bottom to top.
*
* <p>
* A line can contain at most {@code Integer.MAX_VALUE - 8} encoded bytes, excluding its line separator. The reader accumulates a line in memory
* before returning it, so available heap can impose a smaller limit.
* </p>
*
* @return The next line or null if the start of the file is reached.
* @throws IOException Thrown if an I/O error occurs.
* @throws IllegalStateException if the line exceeds the maximum supported number of encoded bytes.
*/
public String readLine() throws IOException {
String line = currentFilePart.readLine();
while (line == null) {
currentFilePart = currentFilePart.rollOver();
if (currentFilePart == null) {
// partNumber more FileParts: we're done, leave line set to null
break;
}
line = currentFilePart.readLine();
}
// aligned behavior with BufferedReader that doesn't return a last, empty line
if (EMPTY_STRING.equals(line) && !trailingNewlineOfFileSkipped) {
trailingNewlineOfFileSkipped = true;
line = readLine();
}
return line;
}
/**
* Returns {@code lineCount} lines of the file from bottom to top.
* <p>
* If there are less than {@code lineCount} lines in the file, then that's what
* you get.
* </p>
* <p>
* Note: You can easily flip the result with {@link Collections#reverse(List)}.
* </p>
*
* @param lineCount How many lines to read.
* @return A new list.
* @throws IOException Thrown if an I/O error occurs.
* @since 2.8.0
*/
public List<String> readLines(final int lineCount) throws IOException {
if (lineCount < 0) {
throw new IllegalArgumentException("lineCount < 0");
}
final ArrayList<String> arrayList = new ArrayList<>(lineCount);
for (int i = 0; i < lineCount; i++) {
final String line = readLine();
if (line == null) {
return arrayList;
}
arrayList.add(line);
}
return arrayList;
}
/**
* Returns the last {@code lineCount} lines of the file.
* <p>
* If there are less than {@code lineCount} lines in the file, then that's what
* you get.
* </p>
*
* @param lineCount How many lines to read.
* @return A String.
* @throws IOException Thrown if an I/O error occurs.
* @since 2.8.0
*/
public String toString(final int lineCount) throws IOException {
final List<String> lines = readLines(lineCount);
Collections.reverse(lines);
return lines.isEmpty() ? EMPTY_STRING : String.join(System.lineSeparator(), lines) + System.lineSeparator();
}
@Override
public Iterable<String> unwrap() {
return null;
}
}