duke@1: /*
ohair@554:  * Copyright (c) 1999, 2006, Oracle and/or its affiliates. All rights reserved.
duke@1:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@1:  *
duke@1:  * This code is free software; you can redistribute it and/or modify it
duke@1:  * under the terms of the GNU General Public License version 2 only, as
ohair@554:  * published by the Free Software Foundation.  Oracle designates this
duke@1:  * particular file as subject to the "Classpath" exception as provided
ohair@554:  * by Oracle in the LICENSE file that accompanied this code.
duke@1:  *
duke@1:  * This code is distributed in the hope that it will be useful, but WITHOUT
duke@1:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@1:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
duke@1:  * version 2 for more details (a copy is included in the LICENSE file that
duke@1:  * accompanied this code).
duke@1:  *
duke@1:  * You should have received a copy of the GNU General Public License version
duke@1:  * 2 along with this work; if not, write to the Free Software Foundation,
duke@1:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@1:  *
ohair@554:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
ohair@554:  * or visit www.oracle.com if you need additional information or have any
ohair@554:  * questions.
duke@1:  */
duke@1: 
duke@1: package com.sun.tools.javac.util;
duke@1: 
duke@1: import java.util.BitSet;
duke@1: import static com.sun.tools.javac.util.LayoutCharacters.*;
duke@1: 
duke@1: /** A class that defines source code positions as simple character
duke@1:  *  offsets from the beginning of the file. The first character
duke@1:  *  is at position 0.
duke@1:  *
duke@1:  *  Support is also provided for (line,column) coordinates, but tab
duke@1:  *  expansion is optional and no Unicode excape translation is considered.
duke@1:  *  The first character is at location (1,1).
duke@1:  *
jjg@581:  *  <p><b>This is NOT part of any supported API.
jjg@581:  *  If you write code that depends on this, you do so at your own risk.
duke@1:  *  This code and its internal interfaces are subject to change or
duke@1:  *  deletion without notice.</b>
duke@1:  */
duke@1: public class Position {
duke@1:     public static final int NOPOS        = -1;
duke@1: 
duke@1:     public static final int FIRSTPOS     = 0;
duke@1:     public static final int FIRSTLINE    = 1;
duke@1:     public static final int FIRSTCOLUMN  = 1;
duke@1: 
duke@1:     public static final int LINESHIFT    = 10;
duke@1:     public static final int MAXCOLUMN    = (1<<LINESHIFT) - 1;
duke@1:     public static final int MAXLINE      = (1<<(Integer.SIZE-LINESHIFT)) - 1;
duke@1: 
duke@1:     public static final int MAXPOS       = Integer.MAX_VALUE;
duke@1: 
duke@1:     /**
duke@1:      * This is class is not supposed to be instantiated.
duke@1:      */
duke@1:     private Position() {}
duke@1: 
duke@1:     /** A two-way map between line/column numbers and positions,
duke@1:      *  derived from a scan done at creation time.  Tab expansion is
duke@1:      *  optionally supported via a character map.  Text content
duke@1:      *  is not retained.
duke@1:      *<p>
duke@1:      *  Notes:  The first character position FIRSTPOS is at
duke@1:      *  (FIRSTLINE,FIRSTCOLUMN).  No account is taken of Unicode escapes.
duke@1:      *
duke@1:      * @param   src         Source characters
duke@1:      * @param   max         Number of characters to read
duke@1:      * @param   expandTabs  If true, expand tabs when calculating columns
duke@1:      */
duke@1:     public static LineMap makeLineMap(char[] src, int max, boolean expandTabs) {
duke@1:         LineMapImpl lineMap = expandTabs ?
duke@1:             new LineTabMapImpl(max) : new LineMapImpl();
duke@1:         lineMap.build(src, max);
duke@1:         return lineMap;
duke@1:     }
duke@1: 
duke@1:     /** Encode line and column numbers in an integer as:
duke@1:      *  line-number << LINESHIFT + column-number
duke@1:      *  {@link Position.NOPOS represents an undefined position.
duke@1:      *
duke@1:      * @param  line  number of line (first is 1)
duke@1:      * @param  col   number of character on line (first is 1)
duke@1:      * @return       an encoded position or {@link Position.NOPOS
duke@1:      *               if the line or column number is too big to
duke@1:      *               represent in the encoded format
duke@1:      * @throws IllegalArgumentException if line or col is less than 1
duke@1:      */
duke@1:     public static int encodePosition(int line, int col) {
duke@1:         if (line < 1)
duke@1:             throw new IllegalArgumentException("line must be greater than 0");
duke@1:         if (col < 1)
duke@1:             throw new IllegalArgumentException("column must be greater than 0");
duke@1: 
duke@1:         if (line > MAXLINE || col > MAXCOLUMN) {
duke@1:             return NOPOS;
duke@1:         }
duke@1:         return (line << LINESHIFT) + col;
duke@1:     }
duke@1: 
duke@1:     public static interface LineMap extends com.sun.source.tree.LineMap {
duke@1:         /** Find the start position of a line.
duke@1:          *
duke@1:          * @param line number of line (first is 1)
duke@1:          * @return     position of first character in line
duke@1:          * @throws  ArrayIndexOutOfBoundsException
duke@1:          *           if <tt>lineNumber < 1</tt>
duke@1:          *           if <tt>lineNumber > no. of lines</tt>
duke@1:          */
duke@1:         int getStartPosition(int line);
duke@1: 
duke@1:         /** Find the position corresponding to a (line,column).
duke@1:          *
duke@1:          * @param   line    number of line (first is 1)
duke@1:          * @param   column  number of character on line (first is 1)
duke@1:          *
duke@1:          * @return  position of character
duke@1:          * @throws  ArrayIndexOutOfBoundsException
duke@1:          *           if <tt>line < 1</tt>
duke@1:          *           if <tt>line > no. of lines</tt>
duke@1:          */
duke@1:         int getPosition(int line, int column);
duke@1: 
duke@1:         /** Find the line containing a position; a line termination
duke@1:          * character is on the line it terminates.
duke@1:          *
duke@1:          * @param   pos  character offset of the position
duke@1:          * @return the line number on which pos occurs (first line is 1)
duke@1:          */
duke@1:         int getLineNumber(int pos);
duke@1: 
duke@1:         /** Find the column for a character position.
duke@1:          *  Note:  this method does not handle tab expansion.
duke@1:          *  If tab expansion is needed, use a LineTabMap instead.
duke@1:          *
duke@1:          * @param  pos   character offset of the position
duke@1:          * @return       the column number at which pos occurs
duke@1:          */
duke@1:         int getColumnNumber(int pos);
duke@1:     }
duke@1: 
duke@1:     static class LineMapImpl implements LineMap {
duke@1:         protected int[] startPosition; // start position of each line
duke@1: 
duke@1:         protected LineMapImpl() {}
duke@1: 
duke@1:         protected void build(char[] src, int max) {
duke@1:             int c = 0;
duke@1:             int i = 0;
duke@1:             int[] linebuf = new int[max];
duke@1:             while (i < max) {
duke@1:                 linebuf[c++] = i;
duke@1:                 do {
duke@1:                     char ch = src[i];
duke@1:                     if (ch == '\r' || ch == '\n') {
duke@1:                         if (ch == '\r' && (i+1) < max && src[i+1] == '\n')
duke@1:                             i += 2;
duke@1:                         else
duke@1:                             ++i;
duke@1:                         break;
duke@1:                     }
duke@1:                     else if (ch == '\t')
duke@1:                         setTabPosition(i);
duke@1:                 } while (++i < max);
duke@1:             }
duke@1:             this.startPosition = new int[c];
duke@1:             System.arraycopy(linebuf, 0, startPosition, 0, c);
duke@1:         }
duke@1: 
duke@1:         public int getStartPosition(int line) {
duke@1:             return startPosition[line - FIRSTLINE];
duke@1:         }
duke@1: 
duke@1:         public long getStartPosition(long line) {
duke@1:             return getStartPosition(longToInt(line));
duke@1:         }
duke@1: 
duke@1:         public int getPosition(int line, int column) {
duke@1:             return startPosition[line - FIRSTLINE] + column - FIRSTCOLUMN;
duke@1:         }
duke@1: 
duke@1:         public long getPosition(long line, long column) {
duke@1:             return getPosition(longToInt(line), longToInt(column));
duke@1:         }
duke@1: 
duke@1:         // Cache of last line number lookup
duke@1:         private int lastPosition = Position.FIRSTPOS;
duke@1:         private int lastLine = Position.FIRSTLINE;
duke@1: 
duke@1:         public int getLineNumber(int pos) {
duke@1:             if (pos == lastPosition) {
duke@1:                 return lastLine;
duke@1:             }
duke@1:             lastPosition = pos;
duke@1: 
duke@1:             int low = 0;
duke@1:             int high = startPosition.length-1;
duke@1:             while (low <= high) {
duke@1:                 int mid = (low + high) >> 1;
duke@1:                 int midVal = startPosition[mid];
duke@1: 
duke@1:                 if (midVal < pos)
duke@1:                     low = mid + 1;
duke@1:                 else if (midVal > pos)
duke@1:                     high = mid - 1;
duke@1:                 else {
duke@1:                     lastLine = mid + 1; // pos is at beginning of this line
duke@1:                     return lastLine;
duke@1:                 }
duke@1:             }
duke@1:             lastLine = low;
duke@1:             return lastLine;  // pos is on this line
duke@1:         }
duke@1: 
duke@1:         public long getLineNumber(long pos) {
duke@1:             return getLineNumber(longToInt(pos));
duke@1:         }
duke@1: 
duke@1:         public int getColumnNumber(int pos) {
duke@1:             return pos - startPosition[getLineNumber(pos) - FIRSTLINE] + FIRSTCOLUMN;
duke@1:         }
duke@1: 
duke@1:         public long getColumnNumber(long pos) {
duke@1:             return getColumnNumber(longToInt(pos));
duke@1:         }
duke@1: 
duke@1:         private static int longToInt(long longValue) {
duke@1:             int intValue = (int)longValue;
duke@1:             if (intValue != longValue)
duke@1:                 throw new IndexOutOfBoundsException();
duke@1:             return intValue;
duke@1:         }
duke@1: 
duke@1:         protected void setTabPosition(int offset) {}
duke@1:     }
duke@1: 
duke@1:     /**
duke@1:      * A LineMap that handles tab expansion correctly.  The cost is
duke@1:      * an additional bit per character in the source array.
duke@1:      */
duke@1:     public static class LineTabMapImpl extends LineMapImpl {
duke@1:         private BitSet tabMap;       // bits set for tab positions.
duke@1: 
duke@1:         public LineTabMapImpl(int max) {
duke@1:             super();
duke@1:             tabMap = new BitSet(max);
duke@1:         }
duke@1: 
duke@1:         protected void setTabPosition(int offset) {
duke@1:             tabMap.set(offset);
duke@1:         }
duke@1: 
duke@1:         public int getColumnNumber(int pos) {
duke@1:             int lineStart = startPosition[getLineNumber(pos) - FIRSTLINE];
duke@1:             int column = 0;
duke@1:             for (int bp = lineStart; bp < pos; bp++) {
duke@1:                 if (tabMap.get(bp))
duke@1:                     column = (column / TabInc * TabInc) + TabInc;
duke@1:                 else
duke@1:                     column++;
duke@1:             }
duke@1:             return column + FIRSTCOLUMN;
duke@1:         }
duke@1: 
duke@1:         public int getPosition(int line, int column) {
duke@1:             int pos = startPosition[line - FIRSTLINE];
duke@1:             column -= FIRSTCOLUMN;
duke@1:             int col = 0;
duke@1:             while (col < column) {
duke@1:                 pos++;
duke@1:                 if (tabMap.get(pos))
duke@1:                     col = (col / TabInc * TabInc) + TabInc;
duke@1:                 else
duke@1:                     col++;
duke@1:             }
duke@1:             return pos;
duke@1:         }
duke@1:     }
duke@1: }