bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/parsing/utils/LineLocators.java

   1 package org.simantics.scl.compiler.internal.parsing.utils;
   2
   3 import gnu.trove.list.array.TIntArrayList;
   4
   5 public class LineLocators {
   6
   7     private static class ByteArrayLineLocator extends LineLocator {
   8         private final byte[] lineNumbers;
   9         private final int maxLine;
  10
  11         public ByteArrayLineLocator(int[] rowStarts) {
  12             super(rowStarts);
  13             int lastRow = rowStarts.length-1;
  14             this.lineNumbers = new byte[rowStarts[lastRow]];
  15             this.maxLine = rowStarts.length-1;
  16
  17             int position = 0;
  18             int line = 0;
  19             while(line < maxLine) {
  20                 int endPosition = rowStarts[line+1];
  21                 while(position < endPosition)
  22                     lineNumbers[position++] = (byte)line;
  23                 ++line;
  24             }
  25         }
  26
  27         @Override
  28         public int lineNumberFromPosition(int position) {
  29             if(position <= 0)
  30                 return 0;
  31             if(position >= lineNumbers.length)
  32                 return maxLine;
  33             return (int)lineNumbers[position];
  34         }
  35     }
  36
  37     private static class CharArrayLineLocator extends LineLocator {
  38         private final char[] lineNumbers;
  39         private final int maxLine;
  40
  41         public CharArrayLineLocator(int[] rowStarts) {
  42             super(rowStarts);
  43             int lastRow = rowStarts.length-1;
  44             this.lineNumbers = new char[rowStarts[lastRow]];
  45             this.maxLine = rowStarts.length-1;
  46
  47             int position = 0;
  48             int line = 0;
  49             while(line < maxLine) {
  50                 int endPosition = rowStarts[line+1];
  51                 while(position < endPosition)
  52                     lineNumbers[position++] = (char)line;
  53                 ++line;
  54             }
  55         }
  56
  57         @Override
  58         public int lineNumberFromPosition(int position) {
  59             if(position <= 0)
  60                 return 0;
  61             if(position >= lineNumbers.length)
  62                 return maxLine;
  63             return (int)lineNumbers[position];
  64         }
  65     }
  66
  67     private static class IntArrayLineLocator extends LineLocator {
  68         private final int[] lineNumbers;
  69         private final int maxLine;
  70
  71         public IntArrayLineLocator(int[] rowStarts) {
  72             super(rowStarts);
  73             int lastRow = rowStarts.length-1;
  74             this.lineNumbers = new int[rowStarts[lastRow]];
  75             this.maxLine = rowStarts.length-1;
  76
  77             int position = 0;
  78             int line = 0;
  79             while(line < maxLine) {
  80                 int endPosition = rowStarts[line+1];
  81                 while(position < endPosition)
  82                     lineNumbers[position++] = line;
  83                 ++line;
  84             }
  85         }
  86
  87         @Override
  88         public int lineNumberFromPosition(int position) {
  89             if(position <= 0)
  90                 return 0;
  91             if(position >= lineNumbers.length)
  92                 return maxLine;
  93             return lineNumbers[position];
  94         }
  95     }
  96
  97     private static class BinarySearchLineLocator extends LineLocator {
  98         public BinarySearchLineLocator(int[] rowStarts) {
  99             super(rowStarts);
 100         }
 101
 102         @Override
 103         public int lineNumberFromPosition(int position) {
 104             if(position <= 0)
 105                 return 0;
 106             if(position >= rowStarts[rowStarts.length-1])
 107                 return rowStarts.length-1;
 108             int low = 0;
 109             int high = rowStarts.length-1;
 110             // invariant, low <= lineNumber < high
 111             while(low < high-1) {
 112                 int middle = (low+high) / 2;
 113                 if(position < rowStarts[middle])
 114                     high = middle;
 115                 else
 116                     low = middle;
 117             }
 118             return low;
 119         }
 120     }
 121
 122     private static class InterpolationSearchLineLocator extends LineLocator {
 123         public InterpolationSearchLineLocator(int[] rowStarts) {
 124             super(rowStarts);
 125         }
 126
 127         @Override
 128         public int lineNumberFromPosition(int position) {
 129             if(position <= 0)
 130                 return 0;
 131             if(position >= rowStarts[rowStarts.length-1])
 132                 return rowStarts.length-1;
 133             int low = 0;
 134             int lowPosition = 0;
 135             int high = rowStarts.length-1;
 136             int highPosition = rowStarts[high];
 137             // invariant, low <= lineNumber < high
 138             while(low < high-1) {
 139                 int delta = (int)((long)(high - low) * (position - lowPosition) / (highPosition - lowPosition));
 140                 int middle = low + delta;
 141                 if(middle == low)
 142                     ++middle;
 143                 if(position < rowStarts[middle]) {
 144                     high = middle;
 145                     highPosition = rowStarts[high];
 146                 }
 147                 else {
 148                     low = middle;
 149                     lowPosition = rowStarts[low];
 150                 }
 151             }
 152             return low;
 153         }
 154     }
 155
 156     public static final LineLocator DUMMY_LOCATOR = new LineLocator(new int[] {0}) {
 157         @Override
 158         public int lineNumberFromPosition(int position) {
 159             return 0;
 160         }
 161     };
 162
 163     private static int[] findRowStarts(String source) {
 164         TIntArrayList rowStarts = new TIntArrayList();
 165         rowStarts.add(0);
 166
 167         int length = source.length();
 168         for(int i=0;i<length;++i) {
 169             char c = source.charAt(i);
 170             if(c == '\n')
 171                 rowStarts.add(i+1);
 172         }
 173         return rowStarts.toArray();
 174     }
 175
 176     public static LineLocator createLineLocator(String source) {
 177         int[] rowStarts = findRowStarts(source);
 178         if(rowStarts.length <= Byte.MAX_VALUE)
 179             return new ByteArrayLineLocator(rowStarts);
 180         else if(rowStarts.length <= Character.MAX_VALUE)
 181             return new CharArrayLineLocator(rowStarts);
 182         else
 183             return new InterpolationSearchLineLocator(rowStarts);
 184     }
 185 }