--- /dev/null
+package org.simantics.scl.compiler.internal.parsing.utils;
+
+import gnu.trove.list.array.TIntArrayList;
+
+public class LineLocators {
+
+ private static class ByteArrayLineLocator extends LineLocator {
+ private final byte[] lineNumbers;
+ private final int maxLine;
+
+ public ByteArrayLineLocator(int[] rowStarts) {
+ super(rowStarts);
+ int lastRow = rowStarts.length-1;
+ this.lineNumbers = new byte[rowStarts[lastRow]];
+ this.maxLine = rowStarts.length-1;
+
+ int position = 0;
+ int line = 0;
+ while(line < maxLine) {
+ int endPosition = rowStarts[line+1];
+ while(position < endPosition)
+ lineNumbers[position++] = (byte)line;
+ ++line;
+ }
+ }
+
+ @Override
+ public int lineNumberFromPosition(int position) {
+ if(position <= 0)
+ return 0;
+ if(position >= lineNumbers.length)
+ return maxLine;
+ return (int)lineNumbers[position];
+ }
+ }
+
+ private static class CharArrayLineLocator extends LineLocator {
+ private final char[] lineNumbers;
+ private final int maxLine;
+
+ public CharArrayLineLocator(int[] rowStarts) {
+ super(rowStarts);
+ int lastRow = rowStarts.length-1;
+ this.lineNumbers = new char[rowStarts[lastRow]];
+ this.maxLine = rowStarts.length-1;
+
+ int position = 0;
+ int line = 0;
+ while(line < maxLine) {
+ int endPosition = rowStarts[line+1];
+ while(position < endPosition)
+ lineNumbers[position++] = (char)line;
+ ++line;
+ }
+ }
+
+ @Override
+ public int lineNumberFromPosition(int position) {
+ if(position <= 0)
+ return 0;
+ if(position >= lineNumbers.length)
+ return maxLine;
+ return (int)lineNumbers[position];
+ }
+ }
+
+ private static class IntArrayLineLocator extends LineLocator {
+ private final int[] lineNumbers;
+ private final int maxLine;
+
+ public IntArrayLineLocator(int[] rowStarts) {
+ super(rowStarts);
+ int lastRow = rowStarts.length-1;
+ this.lineNumbers = new int[rowStarts[lastRow]];
+ this.maxLine = rowStarts.length-1;
+
+ int position = 0;
+ int line = 0;
+ while(line < maxLine) {
+ int endPosition = rowStarts[line+1];
+ while(position < endPosition)
+ lineNumbers[position++] = line;
+ ++line;
+ }
+ }
+
+ @Override
+ public int lineNumberFromPosition(int position) {
+ if(position <= 0)
+ return 0;
+ if(position >= lineNumbers.length)
+ return maxLine;
+ return lineNumbers[position];
+ }
+ }
+
+ private static class BinarySearchLineLocator extends LineLocator {
+ public BinarySearchLineLocator(int[] rowStarts) {
+ super(rowStarts);
+ }
+
+ @Override
+ public int lineNumberFromPosition(int position) {
+ if(position <= 0)
+ return 0;
+ if(position >= rowStarts[rowStarts.length-1])
+ return rowStarts.length-1;
+ int low = 0;
+ int high = rowStarts.length-1;
+ // invariant, low <= lineNumber < high
+ while(low < high-1) {
+ int middle = (low+high) / 2;
+ if(position < rowStarts[middle])
+ high = middle;
+ else
+ low = middle;
+ }
+ return low;
+ }
+ }
+
+ private static class InterpolationSearchLineLocator extends LineLocator {
+ public InterpolationSearchLineLocator(int[] rowStarts) {
+ super(rowStarts);
+ }
+
+ @Override
+ public int lineNumberFromPosition(int position) {
+ if(position <= 0)
+ return 0;
+ if(position >= rowStarts[rowStarts.length-1])
+ return rowStarts.length-1;
+ int low = 0;
+ int lowPosition = 0;
+ int high = rowStarts.length-1;
+ int highPosition = rowStarts[high];
+ // invariant, low <= lineNumber < high
+ while(low < high-1) {
+ int delta = (int)((long)(high - low) * (position - lowPosition) / (highPosition - lowPosition));
+ int middle = low + delta;
+ if(middle == low)
+ ++middle;
+ if(position < rowStarts[middle]) {
+ high = middle;
+ highPosition = rowStarts[high];
+ }
+ else {
+ low = middle;
+ lowPosition = rowStarts[low];
+ }
+ }
+ return low;
+ }
+ }
+
+ public static final LineLocator DUMMY_LOCATOR = new LineLocator(new int[] {0}) {
+ @Override
+ public int lineNumberFromPosition(int position) {
+ return 0;
+ }
+ };
+
+ private static int[] findRowStarts(String source) {
+ TIntArrayList rowStarts = new TIntArrayList();
+ rowStarts.add(0);
+
+ int length = source.length();
+ for(int i=0;i<length;++i) {
+ char c = source.charAt(i);
+ if(c == '\n')
+ rowStarts.add(i+1);
+ }
+ return rowStarts.toArray();
+ }
+
+ public static LineLocator createLineLocator(String source) {
+ int[] rowStarts = findRowStarts(source);
+ if(rowStarts.length <= Byte.MAX_VALUE)
+ return new ByteArrayLineLocator(rowStarts);
+ else if(rowStarts.length <= Character.MAX_VALUE)
+ return new CharArrayLineLocator(rowStarts);
+ else
+ return new InterpolationSearchLineLocator(rowStarts);
+ }
+}