1 /*
2 * Copyright (c) 1999, 2012, 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 com.sun.tools.javac.util;
27
28 import java.util.BitSet;
29
30 import com.sun.tools.javac.util.DefinedBy.Api;
31
32 import static com.sun.tools.javac.util.LayoutCharacters.*;
33
34 /** A class that defines source code positions as simple character
35 * offsets from the beginning of the file. The first character
36 * is at position 0.
37 *
38 * Support is also provided for (line,column) coordinates, but tab
39 * expansion is optional and no Unicode escape translation is considered.
40 * The first character is at location (1,1).
41 *
42 * <p><b>This is NOT part of any supported API.
43 * If you write code that depends on this, you do so at your own risk.
44 * This code and its internal interfaces are subject to change or
45 * deletion without notice.</b>
46 */
47 public class Position {
48 public static final int NOPOS = -1;
49
50 public static final int FIRSTPOS = 0;
51 public static final int FIRSTLINE = 1;
52 public static final int FIRSTCOLUMN = 1;
53
54 public static final int LINESHIFT = 10;
55 public static final int MAXCOLUMN = (1<<LINESHIFT) - 1;
56 public static final int MAXLINE = (1<<(Integer.SIZE-LINESHIFT)) - 1;
57
58 public static final int MAXPOS = Integer.MAX_VALUE;
59
60 /**
61 * This is class is not supposed to be instantiated.
62 */
63 private Position() {}
64
65 /** A two-way map between line/column numbers and positions,
66 * derived from a scan done at creation time. Tab expansion is
67 * optionally supported via a character map. Text content
68 * is not retained.
69 *<p>
70 * Notes: The first character position FIRSTPOS is at
71 * (FIRSTLINE,FIRSTCOLUMN). No account is taken of Unicode escapes.
72 *
73 * @param src Source characters
74 * @param max Number of characters to read
75 * @param expandTabs If true, expand tabs when calculating columns
76 */
77 public static LineMap makeLineMap(char[] src, int max, boolean expandTabs) {
78 LineMapImpl lineMap = expandTabs ?
79 new LineTabMapImpl(max) : new LineMapImpl();
80 lineMap.build(src, max);
81 return lineMap;
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 public 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 static interface LineMap extends com.sun.source.tree.LineMap {
108 /** Find the start position of a line.
109 *
110 * @param line number of line (first is 1)
111 * @return position of first character in line
112 * @throws ArrayIndexOutOfBoundsException
113 * if {@code lineNumber < 1}
114 * if {@code lineNumber > no. of lines}
115 */
116 int getStartPosition(int line);
117
118 /** Find the position corresponding to a (line,column).
119 *
120 * @param line number of line (first is 1)
121 * @param column number of character on line (first is 1)
122 *
123 * @return position of character
124 * @throws ArrayIndexOutOfBoundsException
125 * if {@code line < 1}
126 * if {@code line > no. of lines}
127 */
128 int getPosition(int line, int column);
129
130 /** Find 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 on which pos occurs (first line is 1)
135 */
136 int getLineNumber(int pos);
137
138 /** Find the column for a character position.
139 * Note: this method does not handle tab expansion.
140 * If tab expansion is needed, use a LineTabMap instead.
141 *
142 * @param pos character offset of the position
143 * @return the column number at which pos occurs
144 */
145 int getColumnNumber(int pos);
146 }
147
148 static class LineMapImpl implements LineMap {
149 protected int[] startPosition; // start position of each line
150
151 protected LineMapImpl() {}
152
153 protected void build(char[] src, int max) {
154 int c = 0;
155 int i = 0;
156 int[] linebuf = new int[max];
157 while (i < max) {
158 linebuf[c++] = i;
159 do {
160 char ch = src[i];
161 if (ch == '\r' || ch == '\n') {
162 if (ch == '\r' && (i+1) < max && src[i+1] == '\n')
163 i += 2;
164 else
165 ++i;
166 break;
167 }
168 else if (ch == '\t')
169 setTabPosition(i);
170 } while (++i < max);
171 }
172 this.startPosition = new int[c];
173 System.arraycopy(linebuf, 0, startPosition, 0, c);
174 }
175
176 public int getStartPosition(int line) {
177 return startPosition[line - FIRSTLINE];
178 }
179
180 @DefinedBy(Api.COMPILER_TREE)
181 public long getStartPosition(long line) {
182 return getStartPosition(longToInt(line));
183 }
184
185 public int getPosition(int line, int column) {
186 return startPosition[line - FIRSTLINE] + column - FIRSTCOLUMN;
187 }
188
189 @DefinedBy(Api.COMPILER_TREE)
190 public long getPosition(long line, long column) {
191 return getPosition(longToInt(line), longToInt(column));
192 }
193
194 // Cache of last line number lookup
195 private int lastPosition = Position.FIRSTPOS;
196 private int lastLine = Position.FIRSTLINE;
197
198 public int getLineNumber(int pos) {
199 if (pos == lastPosition) {
200 return lastLine;
201 }
202 lastPosition = pos;
203
204 int low = 0;
205 int high = startPosition.length-1;
206 while (low <= high) {
207 int mid = (low + high) >> 1;
208 int midVal = startPosition[mid];
209
210 if (midVal < pos)
211 low = mid + 1;
212 else if (midVal > pos)
213 high = mid - 1;
214 else {
215 lastLine = mid + 1; // pos is at beginning of this line
216 return lastLine;
217 }
218 }
219 lastLine = low;
220 return lastLine; // pos is on this line
221 }
222
223 @DefinedBy(Api.COMPILER_TREE)
224 public long getLineNumber(long pos) {
225 return getLineNumber(longToInt(pos));
226 }
227
228 public int getColumnNumber(int pos) {
229 return pos - startPosition[getLineNumber(pos) - FIRSTLINE] + FIRSTCOLUMN;
230 }
231
232 @DefinedBy(Api.COMPILER_TREE)
233 public long getColumnNumber(long pos) {
234 return getColumnNumber(longToInt(pos));
235 }
236
237 private static int longToInt(long longValue) {
238 int intValue = (int)longValue;
239 if (intValue != longValue)
240 throw new IndexOutOfBoundsException();
241 return intValue;
242 }
243
244 protected void setTabPosition(int offset) {}
245 }
246
247 /**
248 * A LineMap that handles tab expansion correctly. The cost is
249 * an additional bit per character in the source array.
250 */
251 public static class LineTabMapImpl extends LineMapImpl {
252 private BitSet tabMap; // bits set for tab positions.
253
254 public LineTabMapImpl(int max) {
255 super();
256 tabMap = new BitSet(max);
257 }
258
259 protected void setTabPosition(int offset) {
260 tabMap.set(offset);
261 }
262
263 public int getColumnNumber(int pos) {
264 int lineStart = startPosition[getLineNumber(pos) - FIRSTLINE];
265 int column = 0;
266 for (int bp = lineStart; bp < pos; bp++) {
267 if (tabMap.get(bp))
268 column = (column / TabInc * TabInc) + TabInc;
269 else
270 column++;
271 }
272 return column + FIRSTCOLUMN;
273 }
274
275 public int getPosition(int line, int column) {
276 int pos = startPosition[line - FIRSTLINE];
277 column -= FIRSTCOLUMN;
278 int col = 0;
279 while (col < column) {
280 pos++;
281 if (tabMap.get(pos))
282 col = (col / TabInc * TabInc) + TabInc;
283 else
284 col++;
285 }
286 return pos;
287 }
288 }
289 }