$ // This file is part of NIT ( http://www.nitlanguage.org ).
$ //
$ // Copyright 2008 Jean Privat <jean@pryen.org>
$ // Based on algorithms developped for ( http://www.sablecc.org/ ).
$ //
$ // Licensed under the Apache License, Version 2.0 (the "License");
$ // you may not use this file except in compliance with the License.
$ // You may obtain a copy of the License at
$ //
$ //     http://www.apache.org/licenses/LICENSE-2.0
$ //
$ // Unless required by applicable law or agreed to in writing, software
$ // distributed under the License is distributed on an "AS IS" BASIS,
$ // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
$ // See the License for the specific language governing permissions and
$ // limitations under the License.

$ template make_lexer()

# The lexer extract NIT tokens from an input stream.
# It is better user with the Parser
class Lexer
	super TablesCapable
	# Last peeked token
	var _token: nullable Token

	# Lexer current state
	var _state: Int = 0

	# The source file
	readable var _file: SourceFile

	# Current character in the stream
	var _stream_pos: Int = 0

	# Current line number in the input stream
	var _line: Int = 0

	# Current column in the input stream
	var _pos: Int = 0

	# Was the last character a cariage-return?
	var _cr: Bool = false

$ foreach {lexer_data/state}
	# Constante state values
	private fun state_${translate(@name,"ABCDEFGHIJKLMNOPQRSTUVWXYZ","abcdefghijklmnopqrstuvwxyz")}: Int do return @id end
$ end foreach

	# Create a new lexer for a stream (and a name)
	init(file: SourceFile)
	do
		_file = file
	end

	# Give the next token (but do not consume it)
	fun peek: Token
	do
		while _token == null do
			_token = get_token
		end
		return _token.as(not null)
	end

	# Give and consume the next token
	fun next: Token
	do
		var result = _token
		while result == null do
			result = get_token
		end
		_token = null
		return result
	end

	# Get a token, or null if it is discarded
	private fun get_token: nullable Token
	do
		var dfa_state = 0

		var sp = _stream_pos
		var start_stream_pos = sp
		var start_pos = _pos
		var start_line = _line
		var string = _file.string
		var string_len = string.length

		var accept_state = -1
		var accept_token = -1
		var accept_length = -1
		var accept_pos = -1
		var accept_line = -1

		loop
			if sp >= string_len then
				dfa_state = -1
			else
				var c = string[sp].ascii
				sp += 1

				var cr = _cr
				var line = _line
				var pos = _pos
				if c == 10 then
					if cr then
						cr = false
					        _file.line_starts[line] = sp
					else
						line = line + 1
						pos = 0
					        _file.line_starts[line] = sp
					end
				else if c == 13 then
					line = line + 1
					pos = 0
					cr = true
					_file.line_starts[line] = sp
				else
					pos = pos + 1
					cr = false
				end

				loop
					var old_state = dfa_state
					if dfa_state < -1 then
						old_state = -2 - dfa_state
					end

					dfa_state = -1

					var low = 0
					var high = lexer_goto(old_state, 0) - 1

					if high >= 0 then
						while low <= high do
							var middle = (low + high) / 2
							var offset = middle * 3 + 1 # +1 because length is at 0

							if c < lexer_goto(old_state, offset) then
								high = middle - 1
							else if c > lexer_goto(old_state, offset+1) then
								low = middle + 1
							else
								dfa_state = lexer_goto(old_state, offset+2)
								break
							end
						end
					end
					if dfa_state > -2 then break
				end

				_cr = cr
				_line = line
				_pos = pos
			end

			if dfa_state >= 0 then
				var tok = lexer_accept(dfa_state)
				if tok != -1 then
					accept_state = dfa_state
					accept_token = tok
					accept_length = sp - start_stream_pos
					accept_pos = _pos
					accept_line = _line
				end
			else
				if accept_state != -1 then
					var location = new Location(_file, start_line + 1, accept_line + 1, start_pos + 1, accept_pos)
					_pos = accept_pos
					_line = accept_line
					_stream_pos = start_stream_pos + accept_length
$ foreach {//token}
					if accept_token == ${position()-1} then
$    if {count(transition[@from!=@to])!=0}
						var state_id = _state
$        foreach transition in {transition[@from!=@to]}
						if state_id == ${/parser/lexer_data/state[@name=$transition/@from]/@id} then
							_state = state_${translate(@to,"ABCDEFGHIJKLMNOPQRSTUVWXYZ","abcdefghijklmnopqrstuvwxyz")}
						end
$        end
$    end if
$    if {@parser_index}
$        if {not(@text)}
						var token_text = string.substring(start_stream_pos, accept_length)
						return new @ename.init_tk(token_text, location)
$        else
						return new @ename.init_tk(location)
$        end
$    else
						return null
$    end
					end
$ end foreach
				else
					_stream_pos = sp
					var location = new Location(_file, start_line + 1, start_line + 1, start_pos + 1, start_pos + 1)
					if sp > start_stream_pos then
						var text = string.substring(start_stream_pos, sp-start_stream_pos)
						var token = new PError.init_error("Syntax error: unknown token {text}.", location)
						return token
					else
						var token = new EOF(location)
						return token
					end
				end
			end
		end
	end
end

$ end template



$ template make_lexer_table()
$ foreach {lexer_data/goto_table/state}
$     foreach {row}
$         if {count(goto)!=0}
static const int lexer_goto_row${position()}[] = {
	${count(goto)},
$             foreach {goto}
	@low, @high, @state[-sep ','-]
$             end foreach
};
$         end
$     end foreach
static const int lexer_goto_row_null[] = {0};
const int* const lexer_goto_table[] = {
$     foreach {row}
$         if {count(goto)!=0}
	lexer_goto_row${position()}[-sep ','-]
$         else
	lexer_goto_row_null[-sep ','-]
$         end
$     end foreach
};
$ end foreach

$ foreach {lexer_data/accept_table/state}
const int lexer_accept_table[] = {
	[-foreach {i}-]${.}[-sep ','-][-end foreach-]
};
$ end foreach

$ end template