1 /*
2 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.incubator.code.parser.impl;
27
28 import java.util.BitSet;
29
30 /**
31 * A class that defines source code positions as simple character
32 * offsets from the beginning of the file. The first character
33 * is at position 0.
34 * <p>
35 * Support is also provided for (line,column) coordinates, but tab
36 * expansion is optional and no Unicode escape translation is considered.
37 * The first character is at location (1,1).
38 *
39 * <p><b>This is NOT part of any supported API.
40 * If you write code that depends on this, you do so at your own risk.
41 * This code and its internal interfaces are subject to change or
42 * deletion without notice.</b>
43 */
44 public final class Position {
45 static final int NOPOS = -1;
46
47 static final int FIRSTPOS = 0;
48 static final int FIRSTLINE = 1;
49 static final int FIRSTCOLUMN = 1;
50
51 static final int LINESHIFT = 10;
52 static final int MAXCOLUMN = (1 << LINESHIFT) - 1;
53 static final int MAXLINE = (1 << (Integer.SIZE - LINESHIFT)) - 1;
54
55 static final int MAXPOS = Integer.MAX_VALUE;
56
57 /**
58 * This is class is not supposed to be instantiated.
59 */
60 private Position() {
61 }
62
63 /**
64 * A two-way map between line/column numbers and positions,
65 * derived from a scan done at creation time. Tab expansion is
66 * optionally supported via a character map. Text content
67 * is not retained.
68 * <p>
69 * Notes: The first character position FIRSTPOS is at
70 * (FIRSTLINE,FIRSTCOLUMN). No account is taken of Unicode escapes.
71 *
72 * @param src Source characters
73 * @param max Number of characters to read
74 * @param expandTabs If true, expand tabs when calculating columns
75 */
76 static LineMap makeLineMap(char[] src, int max, boolean expandTabs) {
77 LineMapImpl lineMap = expandTabs ?
78 new LineTabMapImpl(max) : new LineMapImpl();
79 lineMap.build(src, max);
80 return lineMap;
81 }
82
83 /**
84 * Encode line and column numbers in an integer as:
85 * {@code line-number << LINESHIFT + column-number }.
86 * {@link Position#NOPOS} represents an undefined position.
87 *
88 * @param line number of line (first is 1)
89 * @param col number of character on line (first is 1)
90 * @return an encoded position or {@link Position#NOPOS}
91 * if the line or column number is too big to
92 * represent in the encoded format
93 * @throws IllegalArgumentException if line or col is less than 1
94 */
95 static int encodePosition(int line, int col) {
96 if (line < 1)
97 throw new IllegalArgumentException("line must be greater than 0");
98 if (col < 1)
99 throw new IllegalArgumentException("column must be greater than 0");
100
101 if (line > MAXLINE || col > MAXCOLUMN) {
102 return NOPOS;
103 }
104 return (line << LINESHIFT) + col;
105 }
106
107 public interface LineMap {
108 /**
109 * Finds the start position of a line.
110 *
111 * @param line line number (beginning at 1)
112 * @return position of first character in line
113 * @throws IndexOutOfBoundsException if {@code lineNumber < 1}
114 * if {@code lineNumber > no. of lines}
115 */
116 long getStartPosition(long line);
117
118 /**
119 * Finds the position corresponding to a (line,column).
120 *
121 * @param line line number (beginning at 1)
122 * @param column tab-expanded column number (beginning 1)
123 * @return position of character
124 * @throws IndexOutOfBoundsException if {@code line < 1}
125 * if {@code line > no. of lines}
126 */
127 long getPosition(long line, long column);
128
129 /**
130 * Finds the line containing a position; a line termination
131 * character is on the line it terminates.
132 *
133 * @param pos character offset of the position
134 * @return the line number of pos (first line is 1)
135 */
136 long getLineNumber(long pos);
137
138 /**
139 * Finds the column for a character position.
140 * Tab characters preceding the position on the same line
141 * will be expanded when calculating the column number.
142 *
143 * @param pos character offset of the position
144 * @return the tab-expanded column number of pos (first column is 1)
145 */
146 long getColumnNumber(long pos);
147
148 /**
149 * Find the start position of a line.
150 *
151 * @param line number of line (first is 1)
152 * @return position of first character in line
153 * @throws ArrayIndexOutOfBoundsException if {@code lineNumber < 1}
154 * if {@code lineNumber > no. of lines}
155 */
156 int getStartPosition(int line);
157
158 /**
159 * Find the position corresponding to a (line,column).
160 *
161 * @param line number of line (first is 1)
162 * @param column number of character on line (first is 1)
163 * @return position of character
164 * @throws ArrayIndexOutOfBoundsException if {@code line < 1}
165 * if {@code line > no. of lines}
166 */
167 int getPosition(int line, int column);
168
169 /**
170 * Find the line containing a position; a line termination
171 * character is on the line it terminates.
172 *
173 * @param pos character offset of the position
174 * @return the line number on which pos occurs (first line is 1)
175 */
176 int getLineNumber(int pos);
177
178 /**
179 * Find the column for a character position.
180 * Note: this method does not handle tab expansion.
181 * If tab expansion is needed, use a LineTabMap instead.
182 *
183 * @param pos character offset of the position
184 * @return the column number at which pos occurs
185 */
186 int getColumnNumber(int pos);
187 }
188
189 static class LineMapImpl implements LineMap {
190 int[] startPosition; // start position of each line
191
192 LineMapImpl() {
193 }
194
195 void build(char[] src, int max) {
196 int c = 0;
197 int i = 0;
198 int[] linebuf = new int[max];
199 while (i < max) {
200 linebuf[c++] = i;
201 do {
202 char ch = src[i];
203 if (ch == '\r' || ch == '\n') {
204 if (ch == '\r' && (i + 1) < max && src[i + 1] == '\n')
205 i += 2;
206 else
207 ++i;
208 break;
209 } else if (ch == '\t')
210 setTabPosition(i);
211 } while (++i < max);
212 }
213 this.startPosition = new int[c];
214 System.arraycopy(linebuf, 0, startPosition, 0, c);
215 }
216
217 @Override
218 public int getStartPosition(int line) {
219 return startPosition[line - FIRSTLINE];
220 }
221
222 @Override
223 public long getStartPosition(long line) {
224 return getStartPosition(longToInt(line));
225 }
226
227 @Override
228 public int getPosition(int line, int column) {
229 return startPosition[line - FIRSTLINE] + column - FIRSTCOLUMN;
230 }
231
232 @Override
233 public long getPosition(long line, long column) {
234 return getPosition(longToInt(line), longToInt(column));
235 }
236
237 // Cache of last line number lookup
238 private int lastPosition = Position.FIRSTPOS;
239 private int lastLine = Position.FIRSTLINE;
240
241 @Override
242 public int getLineNumber(int pos) {
243 if (pos == lastPosition) {
244 return lastLine;
245 }
246 lastPosition = pos;
247
248 int low = 0;
249 int high = startPosition.length - 1;
250 while (low <= high) {
251 int mid = (low + high) >> 1;
252 int midVal = startPosition[mid];
253
254 if (midVal < pos)
255 low = mid + 1;
256 else if (midVal > pos)
257 high = mid - 1;
258 else {
259 lastLine = mid + 1; // pos is at beginning of this line
260 return lastLine;
261 }
262 }
263 lastLine = low;
264 return lastLine; // pos is on this line
265 }
266
267 @Override
268 public long getLineNumber(long pos) {
269 return getLineNumber(longToInt(pos));
270 }
271
272 @Override
273 public int getColumnNumber(int pos) {
274 return pos - startPosition[getLineNumber(pos) - FIRSTLINE] + FIRSTCOLUMN;
275 }
276
277 @Override
278 public long getColumnNumber(long pos) {
279 return getColumnNumber(longToInt(pos));
280 }
281
282 static int longToInt(long longValue) {
283 int intValue = (int) longValue;
284 if (intValue != longValue)
285 throw new IndexOutOfBoundsException();
286 return intValue;
287 }
288
289 void setTabPosition(int offset) {
290 }
291 }
292
293 /**
294 * A LineMap that handles tab expansion correctly. The cost is
295 * an additional bit per character in the source array.
296 */
297 static class LineTabMapImpl extends LineMapImpl {
298 private final BitSet tabMap; // bits set for tab positions.
299
300 LineTabMapImpl(int max) {
301 super();
302 tabMap = new BitSet(max);
303 }
304
305 @Override
306 void setTabPosition(int offset) {
307 tabMap.set(offset);
308 }
309
310 @Override
311 public int getColumnNumber(int pos) {
312 int lineStart = startPosition[getLineNumber(pos) - FIRSTLINE];
313 int column = 0;
314 for (int bp = lineStart; bp < pos; bp++) {
315 if (tabMap.get(bp))
316 column = tabulate(column);
317 else
318 column++;
319 }
320 return column + FIRSTCOLUMN;
321 }
322
323 @Override
324 public int getPosition(int line, int column) {
325 int pos = startPosition[line - FIRSTLINE];
326 column -= FIRSTCOLUMN;
327 int col = 0;
328 while (col < column) {
329 pos++;
330 if (tabMap.get(pos))
331 col = tabulate(col);
332 else
333 col++;
334 }
335 return pos;
336 }
337 }
338
339 /**
340 * Tabulator column increment.
341 */
342 static final int TabInc = 8;
343
344 /**
345 * Bump column to the next tab.
346 */
347 static int tabulate(int column) {
348 return (column / TabInc * TabInc) + TabInc;
349 }
350 }