# Find location of production nodes
# Uses existing token locations to infer location of productions.
private class ComputeProdLocationVisitor
	super Visitor

	# The current (or starting) cursor on the token sequence used to collect loose tokens
	var token: nullable Token

	# Currently visited productions that need a first token
	var need_first_prods = new Array[Prod]

	# Already visited epsilon productions that waits something after them
	var need_after_epsilons = new Array[Prod]

	# The last visited token in the current production
	var last_token: nullable Token = null

	redef fun visit(n: ANode)
	do
		if n isa Token then
			# Skip injected tokens
			if not isset n._location then return

			# Collect loose tokens (not in the AST) and attach them to token in the AST
			var cursor = token
			if n != cursor then
				var lt = last_token
				# In order, we have the tokens:
				# * `lt` the previous visited token in the AST (if any)
				# * then `cursor` the loose tokens to attach
				# * then `n` the current visited token in the AST

				# In the following, we advance `cursor` to add them to `lt.next_looses` or to `n.prev_looses`.
				if lt != null then
					var ltl = lt.location.line_end
					# floating tokens on the same line of a AST-token follows it
					while cursor != null and cursor != n and ltl == cursor.location.line_start do
						cursor.is_loose = true
						lt.next_looses.add cursor
						cursor = cursor.next_token
					end
				end
				# other loose tokens precede the next AST-token
				while cursor != null and cursor != n do
					cursor.is_loose = true
					n.prev_looses.add cursor
					cursor = cursor.next_token
				end
			end
			token = n.next_token

			var loc = n._location
			_last_token = n

			# Add a first token to productions that need one
			if not _need_first_prods.is_empty then
				for no in _need_first_prods do
					no._first_location = loc
				end
				_need_first_prods.clear
			end

			# Find location for already visited epsilon production that need one
			if not _need_after_epsilons.is_empty then
				var loco = new Location(loc.file, loc.line_start, loc.line_start, loc.column_start, loc.column_start) 
				for no in _need_after_epsilons do
					no.location = loco
				end
				_need_after_epsilons.clear
			end
		else
			assert n isa Prod
			_need_first_prods.add(n)

			n.visit_all(self)

			var startl = n._first_location
			if startl != null then
				# Non-epsilon production
				var endl = _last_token.location

				if startl == endl then
					n.location = startl
				else
					n.location = new Location(startl.file, startl.line_start, endl.line_end, startl.column_start, endl.column_end)
				end

				if not _need_after_epsilons.is_empty then
					var loc = new Location(endl.file, endl.line_end, endl.line_end, endl.column_end, endl.column_end)
					for no in _need_after_epsilons do
						# Epsilon production that finishes the current non-epsilon production
						no.location = loc
					end
					_need_after_epsilons.clear
				end
			else
				# Epsilon production in the middle or that finishes a parent non-epsilon production
				_need_after_epsilons.add(n)
			end
		end
	end
end