X-Git-Url: https://gerrit.simantics.org/r/gitweb?p=simantics%2Fplatform.git;a=blobdiff_plain;f=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Fparsing%2Futils%2FLineLocators.java;fp=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Fparsing%2Futils%2FLineLocators.java;h=63b2baf7b16f9c59828cedf6a8c77a55fde62f7e;hp=0000000000000000000000000000000000000000;hb=91682baa9a8252390f09b80fd724f47e5957b234;hpb=3826e289058a51d09310b7ba1251e959dc0ed3d0

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/parsing/utils/LineLocators.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/parsing/utils/LineLocators.java
new file mode 100644
index 000000000..63b2baf7b
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/parsing/utils/LineLocators.java
@@ -0,0 +1,185 @@
+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);
+    }
+}