// Copyright 2018 The Jadep Authors
//
// 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.

// Package ast provides a basic tree implementation for storing an AST generated by a parser.
//
// The AST is represented as a []byte. The first four bytes contain the format version, the type of
// the AST, and the main language of the file. The last byte contains the offset to the root node
// (there is always exactly one root node).
//
// Siblings are adjacent in the buffer and children always preceed parents.
// For declaratives ASTs, interesting substrings of the source text (e.g., identifier names) are
// placed before the first set of siblings in which they are referenced, and they are reused for
// later occurences of the same text.
//
// Current layout of a serialized node:
// - Flags (uint8, required)
// - Relative offset to previous sibling (uint8, required)
// - Type (uint16, required)
// - Relative offset to parent (uint32, required)
// - offset within source file (uint16 or uint32, optional)
// - (Full-only) endOffset within source file (uint16 or uint32, optional)
//   OR
//   (Declarative-only) Relative offset to the node's text (uint16 or uint32, optional)
// - Relative offset to first child (uint16 or uint32, optional)
package ast

import (
	"encoding/binary"
	"errors"
	"fmt"

	lpb "github.com/bazelbuild/tools_jvm_autodeps/thirdparty/golang/parsers/lang"
	"github.com/bazelbuild/tools_jvm_autodeps/thirdparty/golang/parsers/node"
	"github.com/bazelbuild/tools_jvm_autodeps/thirdparty/golang/parsers/parsers"
	"github.com/bazelbuild/tools_jvm_autodeps/thirdparty/golang/parsers/util/offset"
	"context"
)

// Type is the type of the AST.
type Type uint8

const (
	// Full ASTs contain are intended to be used for local modifications and refactorings of the
	// currently open file. They contain all node types and can reference the file content, provided
	// as a separate string.
	Full Type = 0
	// Declarative ASTs are intended to be cached for "background" files (all files except for the one
	// currently being edited). They don’t have comments, keywords, punctuation characters and method
	// bodies and don't support the Offset() and EndOffset() methods. However, relevant parts of the
	// source text are stored directly within the serialized buffer (e.g., identifier names).
	Declarative Type = 1
)

var (
	errTooSmall    = errors.New("byte buffer too small")
	errWrongFormat = errors.New("byte buffer has wrong format version")
)

// Options contains parameters that control the shape of the produced AST.
type Options struct {
	// Adds node.Punctuation and node.Keyword nodes to the parse tree.
	IncludeAllTokens bool

	// A callback function which decides whether the parser should try to recover
	// and continue parsing. If it decides to abort the processing, the last error
	// gets returned as the main outcome from the parser. Successful error
	// recovery leads to one or more SyntaxProblem or InvalidToken nodes in
	// the tree.
	//
	// Never called on syntactically valid input.
	// Leave unset to disable error recovery.
	ShouldTryToRecover func(err parsers.SyntaxError) bool

	// Expand the regions of some nodes to include preceding comments.
	AttachCommentsToNodes bool

	// The type of AST to construct.
	Type Type
}

// AlwaysRecover turns on unconditional recovery if found in the Options.ShouldTryToRecover field.
func AlwaysRecover(err parsers.SyntaxError) bool { return true }

// Node is an element of the AST. It stores information necessary to extract the node data
// (type, offsets) and the relatives of the node (parent, siblings, etc.) from the AST buffer.
//
// A Node is intended to be passed by value (currently 16 bytes).
//
// Node follows the Null Object Pattern. Getting a non-existent relative of a Node returns
// an empty Node object, for which IsValid() returns false and all other methods return default
// values.
type Node struct {
	index uint32    // serialized data offset in tree.buffer
	flags nodeFlags // describes which information about this node is stored in the blob
	size  uint8     // size of the serialized data
	tree  *Tree
}

// Tree returns the tree that the node belongs to.
func (n Node) Tree() *Tree {
	return n.tree
}

// IsValid returns whether the node exists.
// For example, n.NextSibling().IsValid() returns false if n has no next sibling.
func (n Node) IsValid() bool {
	return n.index != 0
}

// Type returns the node's type.
func (n Node) Type() node.Type {
	if n.IsValid() {
		return node.Type(binary.LittleEndian.Uint16(n.tree.buffer[int(n.index)+typePos:]))
	}
	return node.NoType
}

// LocalID returns a unique id of this node within the current file.
func (n Node) LocalID() uint32 {
	return n.index
}

// Offset returns the node's 0-based byte offset in the source content.
func (n Node) Offset() int {
	if getFlag(n.flags, hasOffsetsPos) || getFlag(n.flags, hasTextPos) {
		buf := n.tree.buffer[int(n.index)+offsetOrTextPos:]
		return readInt(buf, getFlag(n.flags, hasBigOffsetsPos))
	}
	return 0
}

// EndOffset returns the node's 0-based byte end offset in the source content.
func (n Node) EndOffset() int {
	if getFlag(n.flags, hasOffsetsPos) {
		bigOffsets := 1 & (n.flags >> hasBigOffsetsPos)
		pos := offsetOrTextPos + 2 + (bigOffsets << 1)
		buf := n.tree.buffer[n.index+uint32(pos):]
		return readInt(buf, bigOffsets > 0)
	}
	if getFlag(n.flags, hasTextPos) {
		return n.Range().EndOffset
	}
	return 0
}

// Range returns the range of the node in the source content.
// This is more efficient than calling n.Offset() and n.EndOffset() separately.
func (n Node) Range() offset.Range {
	if getFlag(n.flags, hasOffsetsPos) {
		buf := n.tree.buffer[int(n.index)+offsetOrTextPos:]
		bigOffsets := 1 & (n.flags >> hasBigOffsetsPos)
		hasBigOffsets := bigOffsets != 0
		startOffset := readInt(buf, hasBigOffsets)
		buf = buf[2+(bigOffsets<<1):]
		endOffset := readInt(buf, hasBigOffsets)
		return offset.Range{startOffset, endOffset}
	}
	if getFlag(n.flags, hasTextPos) {
		buf := n.tree.buffer
		bigOffsets := 1 & (n.flags >> hasBigOffsetsPos)
		pos := int(n.index) + offsetOrTextPos
		startOffset := readInt(buf[pos:], bigOffsets != 0)
		pos += 2 + int(bigOffsets<<1)
		index := int(n.index) - readInt(buf[pos:], getFlag(n.flags, hasBigTextPos))
		if size, n := binary.Uvarint(buf[index:]); n > 0 {
			return offset.Range{startOffset, startOffset + int(size)}
		}
	}
	return offset.Range{}
}

// Text returns a substring of the source text, bounded by the offsets: [offset, endOffset).
// If the offsets are invalid, an empty string is returned.
// For declarative ASTs, Text() only returns non-empty for nodes whose text has been nested
// in the serialized AST (e.g., identifiers).
func (n Node) Text() string {
	// First check if the text for this node is nested within the buffer.
	if getFlag(n.flags, hasTextPos) {
		buf := n.tree.buffer
		bigOffsets := 1 & (n.flags >> hasBigOffsetsPos)
		pos := int(n.index) + offsetOrTextPos + 2 + int(bigOffsets<<1)
		index := int(n.index) - readInt(buf[pos:], getFlag(n.flags, hasBigTextPos))
		if size, n := binary.Uvarint(buf[index:]); n > 0 {
			start := index + n
			return string(buf[start : start+int(size)])
		}
		return ""
	}
	// Otherwise, attempt to extract the text from the source (if available).
	if getFlag(n.flags, hasOffsetsPos) {
		r := n.Range()
		if r.Offset >= 0 && r.EndOffset <= len(n.tree.source) {
			return n.tree.source[r.Offset:r.EndOffset]
		}
	}
	return ""
}

// Parent returns the node's parent node or an invalid node if there isn't any.
func (n Node) Parent() Node {
	if n.IsValid() {
		if offset := binary.LittleEndian.Uint32(n.tree.buffer[n.index+parentPos:]); offset > 0 {
			return unpack(n.tree, int(n.index)+int(offset))
		}
	}
	return Node{}
}

// FirstChild returns the first child of the node or an invalid node if it there isn't any.
func (n Node) FirstChild() Node {
	if getFlag(n.flags, hasChildrenPos) {
		bigIdx := 1 & (n.flags >> hasBigFirstChildPos)
		pos := n.size - 2 - (uint8(bigIdx) << 1)
		buf := n.tree.buffer[n.index+uint32(pos):]
		offset := readInt(buf, bigIdx > 0)
		return unpack(n.tree, int(n.index)-offset)
	}
	return Node{}
}

// NextSibling returns the next sibling of a node or an invalid node if there isn't any.
func (n Node) NextSibling() Node {
	if getFlag(n.flags, hasNextSiblingPos) {
		return unpack(n.tree, int(n.index)+int(n.size))
	}
	return Node{}
}

// PrevSibling returns the previous sibling of a node or an invalid node if there isn't any.
func (n Node) PrevSibling() Node {
	if n.IsValid() {
		if offset := n.tree.buffer[n.index+prevSiblingPos]; offset > 0 {
			return unpack(n.tree, int(n.index)-int(offset))
		}
	}
	return Node{}
}

func (n Node) String() string {
	if !n.IsValid() {
		return "nil"
	}
	if getFlag(n.flags, hasOffsetsPos) {
		return fmt.Sprintf("%v(%v)", n.Type(), n.Range())
	}
	return fmt.Sprintf("%v(%v)", n.Type(), n.Text())
}

// ChildrenOfType returns all the direct children with the specified type.
func (n Node) ChildrenOfType(t node.Type) (nodes []Node) {
	for child := n.FirstChild(); child.IsValid(); child = child.NextSibling() {
		if child.Type() == t {
			nodes = append(nodes, child)
		}
	}
	return
}

// FirstChildOfType returns the first child with the specified type or an invalid node
// if not found.
func (n Node) FirstChildOfType(t node.Type) Node {
	child := n.FirstChild()
	for ; child.IsValid() && child.Type() != t; child = child.NextSibling() {
	}
	return child
}

// LastChildOfType returns the last child with the specified type or an invalid node
// if not found.
func (n Node) LastChildOfType(t node.Type) Node {
	var ret Node
	for child := n.FirstChild(); child.IsValid(); child = child.NextSibling() {
		if child.Type() == t {
			ret = child
		}
	}
	return ret
}

// Child returns the first child that matches the provided selector.
func (n Node) Child(sel node.Selector) Node {
	for child := n.FirstChild(); child.IsValid(); child = child.NextSibling() {
		if sel(child.Type()) {
			return child
		}
	}
	return Node{}
}

// Children returns all children nodes that match the provided selector.
func (n Node) Children(sel node.Selector) []Node {
	var ret []Node
	for child := n.FirstChild(); child.IsValid(); child = child.NextSibling() {
		if sel(child.Type()) {
			ret = append(ret, child)
		}
	}
	return ret
}

// Index returns the 0-based position of the node among its siblings matching the given selector.
// Returns -1 for invalid nodes.
func (n Node) Index(sel node.Selector) int {
	pos := -1
	for n.IsValid() {
		if sel(n.Type()) {
			pos++
		}
		n = n.PrevSibling()
	}
	return pos
}

// Prev returns the first element among the previous siblings that matches the selector.
func (n Node) Prev(sel node.Selector) Node {
	for sib := n.PrevSibling(); sib.IsValid(); sib = sib.PrevSibling() {
		if sel(sib.Type()) {
			return sib
		}
	}
	return Node{}
}

// Next returns the first element among the following siblings that matches the selector.
func (n Node) Next(sel node.Selector) Node {
	for sib := n.NextSibling(); sib.IsValid(); sib = sib.NextSibling() {
		if sel(sib.Type()) {
			return sib
		}
	}
	return Node{}
}

// NextAll returns all following siblings of the node that match the selector.
func (n Node) NextAll(sel node.Selector) []Node {
	var ret []Node
	for sib := n.NextSibling(); sib.IsValid(); sib = sib.NextSibling() {
		if sel(sib.Type()) {
			ret = append(ret, sib)
		}
	}
	return ret
}

// Container returns the innermost container node that matches the provided selector.
func (n Node) Container(sel node.Selector) Node {
	for parent := n.Parent(); parent.IsValid(); parent = parent.Parent() {
		if sel(parent.Type()) {
			return parent
		}
	}
	return Node{}
}

// Descend descends into the AST layer by layer picking the next node among children of the previous
// node. This method is equivalent to a chain of Child() calls.
func (n Node) Descend(sels ...node.Selector) Node {
	for _, sel := range sels {
		n = n.Child(sel)
	}
	return n
}

// Traverse does a pre-order traversal of the subtree starting at this node.
// The provided visitor method can return false to skip children of the visited node.
func (n Node) Traverse(visitor func(n Node) bool) {
	if !n.IsValid() || !visitor(n) {
		return
	}

	for child := n.FirstChild(); child.IsValid(); child = child.NextSibling() {
		child.Traverse(visitor)
	}
}

// Tree represents a language independent tree representation of the code as produced
// by parsers.
type Tree struct {
	buffer []byte         // holds the serialized version of the AST.
	path   string         // path or URI that identifies the source code location
	source string         // source code
	mapper *offset.Mapper // helper for mapping between global offsets and (line, column) values.
	t      Type           // type of the AST
	lang   lpb.Language   // the language of the file
}

// Type returns the type of the tree.
func (tree *Tree) Type() Type {
	return tree.t
}

// Root returns the tree's root node.
func (tree *Tree) Root() Node {
	if len(tree.buffer) == 0 {
		return Node{}
	}

	// The size of the root node is stored in the last byte of the buffer.
	size := len(tree.buffer)
	index := size - int(tree.buffer[size-1]) - 1
	return unpack(tree, index)
}

// NodeByID returns a node by its local ID.
func (tree *Tree) NodeByID(localID uint32) Node {
	return unpack(tree, int(localID))
}

// ForEach iterates over all AST nodes that match a given selector (children before parents).
func (tree *Tree) ForEach(sel node.Selector, consumer func(n Node)) {
	if tree.t != Full {
		return
	}
	for n := unpack(tree, firstNodeOffset); n.IsValid(); n = unpack(tree, int(n.index)+int(n.size)) {
		if sel(n.Type()) {
			consumer(n)
		}
	}
}

// Buffer returns a slice of bytes that contain the serialized version of the AST,
// to be used for transmission and storage.
func (tree *Tree) Buffer() []byte {
	return tree.buffer
}

// Mapper returns the tree's offset mapper for exposing offset helper methods.
func (tree *Tree) Mapper() *offset.Mapper {
	return tree.mapper
}

// Path returns the location of the parsed source code.
//
// Note: this function returns what was provided during the AST creation, so this can be either a
// relative or absolute path, or even a URI, depending on where this tree is coming from.
func (tree *Tree) Path() string {
	return tree.path
}

// Text returns the underlying source code (for full ASTs only)
func (tree *Tree) Text() string {
	return tree.source
}

// Language returns the language of the file.
func (tree *Tree) Language() lpb.Language {
	return tree.lang
}

// NodeByOffset returns the most specific node found at that offset or an invalid node if that
// offset is not covered by any node. If the cursor is placed between two touching nodes, we prefer
// the one that looks like an identifier (an identifier cannot start right after another
// identifier) and by default take the first one.
func (tree *Tree) NodeByOffset(offset int) Node {
	n := tree.Root()
	if tree.t != Full || !n.IsValid() || !n.Range().Contains(offset) {
		return Node{}
	}
	var second Node
	for child := n.FirstChild(); child.IsValid(); {
		if r := child.Range(); !r.Empty() && r.Contains(offset) {
			n = child
			child = n.FirstChild()
			if offset == r.EndOffset && !second.IsValid() {
				for sibl := n.NextSibling(); sibl.Offset() == offset; sibl = sibl.NextSibling() {
					// Ignore empty nodes in between.
					if sibl.EndOffset() > offset {
						second = sibl
						break
					}
				}
			}
			continue
		}
		child = child.NextSibling()
	}

	if !second.IsValid() {
		return n
	}

	// Descend into the second branch.
	for child := second.FirstChild(); child.IsValid(); {
		if r := child.Range(); !r.Empty() && r.Contains(offset) {
			second = child
			child = second.FirstChild()
			continue
		}
		child = child.NextSibling()
	}

	if second.Type().HasProperty(node.IdentifierLike) {
		return second
	}
	return n
}

// NodeByRange returns the innermost node that fully contains the given range.
// Empty ranges are not supported.
func (tree *Tree) NodeByRange(r offset.Range) Node {
	n := tree.Root()
	if tree.t != Full || r.Empty() || !n.IsValid() || !n.Range().ContainsRange(r) {
		return Node{}
	}
	for child := n.FirstChild(); child.IsValid(); {
		if cr := child.Range(); cr.ContainsRange(r) {
			n = child
			child = n.FirstChild()
			continue
		}
		child = child.NextSibling()
	}
	return n
}

// Constants for AST serialization.
const (
	// Current serialization format version.
	formatVersion = 0

	// First node offset in a tree buffer.
	firstNodeOffset = 4

	// Maximum and minumum sizes of a serialized AST node.
	minNodeBytes = offsetOrTextPos
	maxNodeBytes = minNodeBytes + 3*4 // offsets and firstChild, 4 bytes each

	// Absolute byte positions within serialized AST node.
	flagsPos        = 0
	prevSiblingPos  = 1
	typePos         = 2
	parentPos       = 4
	offsetOrTextPos = 8

	// Note: the last 2 or 4 (when hasBigFirstChildPos is set) bytes of the serialized node blob
	// contain the offset of the first child.
)

type nodeFlags uint8

// Positions within the flags byte.
const (
	hasChildrenPos      nodeFlags = 0
	hasBigFirstChildPos nodeFlags = 1
	hasNextSiblingPos   nodeFlags = 2
	hasOffsetsPos       nodeFlags = 3
	hasBigOffsetsPos    nodeFlags = 4
	hasTextPos          nodeFlags = 5
	hasBigTextPos       nodeFlags = 6
)

func setFlag(f nodeFlags, pos nodeFlags, set bool) nodeFlags {
	if set {
		return f | (1 << pos)
	}
	return f
}

func getFlag(f nodeFlags, pos nodeFlags) bool {
	return f&(1<<pos) > 0
}

func appendInt(buf []byte, val int, use4Bytes bool) int {
	if use4Bytes {
		binary.LittleEndian.PutUint32(buf, uint32(val))
		return 4
	}
	binary.LittleEndian.PutUint16(buf, uint16(val))
	return 2
}

func readInt(buf []byte, use4Bytes bool) int {
	if use4Bytes {
		return int(binary.LittleEndian.Uint32(buf))
	}
	return int(binary.LittleEndian.Uint16(buf))
}

// unpack extracts the node located at index idx from the buffer in the given tree,
// or an invalid node if a problem occurs (i.e., the serialized AST is corrupted).
func unpack(tree *Tree, idx int) Node {
	buf := tree.buffer

	if idx >= 0 && idx+minNodeBytes < len(buf) {
		flags := buf[idx+flagsPos]

		size := uint8(minNodeBytes)
		size += (1 & (flags >> hasOffsetsPos) << 2) << (1 & (flags >> hasBigOffsetsPos))
		size += (1 & (flags >> hasTextPos) << 1) << (1 & (flags >> hasBigOffsetsPos))
		size += (1 & (flags >> hasTextPos) << 1) << (1 & (flags >> hasBigTextPos))
		size += (1 & (flags >> hasChildrenPos) << 1) << (1 & (flags >> hasBigFirstChildPos))

		return Node{
			index: uint32(idx),
			flags: nodeFlags(flags),
			size:  size,
			tree:  tree,
		}
	}
	return Node{}
}

// stackElem holds information for each parsed node while its children are processed.
type stackElem struct {
	t             node.Type
	r             offset.Range
	firstChildIdx int
	subtreeIdx    int
	textIdx       int
}

type textElem struct {
	index int
	text  string
}

// builder builds an AST from the node information produced by the parsers.
type builder struct {
	opts    Options
	stack   []stackElem
	texts   []textElem
	textMap map[string]int // string -> its index in texts
	buffer  []byte
	lang    lpb.Language
	path    string
	source  string
	err     error
}

// Serializes a node and appends it to the end of the buffer.
// Returns the index of the new node within the buffer.
func (b *builder) pack(se *stackElem, prevSiblingIdx int) int {
	buf := b.buffer
	newNodeIdx := len(buf)

	// Temporary buffer for the node.
	var node [maxNodeBytes]byte

	hasChildren := se.firstChildIdx > 0
	firstChildRel := newNodeIdx - se.firstChildIdx
	hasBigFirstChild := firstChildRel >= 1<<16
	hasOffsets := b.opts.Type == Full
	hasBigOffsets := se.r.Offset >= 1<<16 || se.r.EndOffset >= 1<<16
	hasText := se.textIdx > 0
	textRel := newNodeIdx - se.textIdx
	hasBigText := textRel >= 1<<16

	// Flags (uint8).
	var flags nodeFlags
	flags = setFlag(flags, hasChildrenPos, hasChildren)
	flags = setFlag(flags, hasOffsetsPos, hasOffsets)
	flags = setFlag(flags, hasBigOffsetsPos, hasBigOffsets)
	flags = setFlag(flags, hasBigFirstChildPos, hasBigFirstChild)
	flags = setFlag(flags, hasTextPos, hasText)
	flags = setFlag(flags, hasBigTextPos, hasBigText)
	node[flagsPos] = uint8(flags)

	if prevSiblingIdx > 0 {
		// Relative offset to previous sibling (uint8).
		node[prevSiblingPos] = byte(newNodeIdx - prevSiblingIdx)

		// Set the previous sibling's hasNextSibling flag.
		buf[prevSiblingIdx+flagsPos] |= 1 << hasNextSiblingPos

		// Temporarily use the space for the previous sibling's parent index to store a reference to
		// this node. This makes traversal of children more efficient in setParents().
		binary.LittleEndian.PutUint32(buf[prevSiblingIdx+parentPos:], uint32(newNodeIdx))
	}

	// Type (uint16).
	binary.LittleEndian.PutUint16(node[typePos:], uint16(se.t))

	size := offsetOrTextPos
	if hasOffsets {
		// offset (uint16 or uint32).
		size += appendInt(node[offsetOrTextPos:], se.r.Offset, hasBigOffsets)
		// endOffset (uint16 or uint32).
		size += appendInt(node[size:], se.r.EndOffset, hasBigOffsets)
	} else if hasText {
		// offset (uint16 or uint32).
		size += appendInt(node[offsetOrTextPos:], se.r.Offset, hasBigOffsets)
		// text (uint16 or uint32).
		size += appendInt(node[size:], textRel, hasBigText)
	}

	// Relative offset to the first child (uint16 or uint32).
	if hasChildren {
		size += appendInt(node[size:], firstChildRel, hasBigFirstChild)
	}

	b.buffer = append(buf, node[:size]...)
	return newNodeIdx
}

// Traverse the children of the parent node and update their parent relationship.
// If parentIdx is 0, the children will have no parent. This is used for the root node.
func (b *builder) setParents(firstChildIdx int, parentIdx int) {
	next := 0
	for i := firstChildIdx; i > 0; i = next {
		// Store relative offset to parent (uint32).
		var parentOffset int
		if parentIdx > 0 {
			parentOffset = parentIdx - i
		}
		next = int(binary.LittleEndian.Uint32(b.buffer[i+parentPos:]))
		binary.LittleEndian.PutUint32(b.buffer[i+parentPos:], uint32(parentOffset))
	}
}

func (b *builder) packText(text string) int {
	index := len(b.buffer)
	var size [binary.MaxVarintLen64]byte
	n := binary.PutUvarint(size[:], uint64(len(text)))
	b.buffer = append(b.buffer, size[:n]...)
	b.buffer = append(b.buffer, []byte(text)...)
	return index
}

// Checks whether the given nodes are separated by at most one newline character
// and any number of tabs and spaces.
func (b *builder) areAdjacent(prev, next *stackElem) bool {
	newlineSeen := false
	for _, c := range b.source[prev.r.EndOffset:next.r.Offset] {
		switch c {
		case '\n':
			if newlineSeen {
				return false
			}
			newlineSeen = true
		case ' ', '\t', '\r':
			continue
		default:
			return false
		}
	}
	return true
}

// Checks whether 'prev' is a comment that should be prepended to 'next'.
func (b *builder) shouldTakeComment(prev, next *stackElem) bool {
	if prev.t.Category() != node.Comment || !b.areAdjacent(prev, next) {
		return false
	}

	if next.t.Category() != node.Comment {
		return true
	}

	// We take sequences of non-multiline comments, but otherwise stop after the first one.
	return !prev.t.HasProperty(node.IsMultilineToken) && !next.t.HasProperty(node.IsMultilineToken)
}

func (b *builder) addNodeToBuffer(se *stackElem, prevSiblingIdx int) (nodeIdx int) {
	// Serialize the node and append it to the buffer.
	index := b.pack(se, prevSiblingIdx)

	// Fix the 'parent' relationship for the children of the new node.
	b.setParents(se.firstChildIdx, index)

	return index
}

// addNode implements the parsers.Listener function type.
// addNode is called whenever the parser emits a new node, for being stored in the AST.
func (b *builder) addNode(t node.Type, startOffset, endOffset int) {
	se := stackElem{
		t:          t,
		r:          offset.Range{startOffset, endOffset},
		subtreeIdx: len(b.buffer),
	}

	size := len(b.stack)
	start := size
	end := start
	for start > 0 && startOffset < b.stack[start-1].r.EndOffset {
		start--
	}
	// Most of the time we get nodes in the order of increasing endOffset but not always.
	for end > start && endOffset < b.stack[end-1].r.EndOffset {
		end--
	}

	// Check that nodes are reported in order, i.e. existing nodes on the stack either do not overlap
	// with the added one, or are fully consumed by it.
	if start < size {
		if startOffset > b.stack[start].r.Offset && b.err == nil {
			b.err = fmt.Errorf("%v parser error: overlapping nodes reported: %v vs %v", b.lang, t, b.stack[start].t)
		} else if end < size && endOffset > b.stack[end].r.Offset && b.err == nil {
			b.err = fmt.Errorf("%v parser error: overlapping nodes reported: %v vs %v", b.lang, t, b.stack[end].t)
		}
	}

	if startOffset == endOffset {
		// Prevent empty nodes becoming parents of other empty nodes.
		end = start
	} else if b.opts.AttachCommentsToNodes && t.HasProperty(node.AttractsComments) {
		// Consume all preceding comments if supported by the element.
		next := &se
		for start > 0 && b.shouldTakeComment(&b.stack[start-1], next) {
			start--
			se.r.Offset = b.stack[start].r.Offset
			next = &b.stack[start]
		}
	}

	if b.opts.Type == Declarative {
		// Compute the start index of the subtree of the current node.
		if start < end {
			se.subtreeIdx = b.stack[start].subtreeIdx
		}

		if t.HasProperty(node.IsLocal) {
			// This node and its entire subtree should not appear in a declarative AST.
			// We assume that the current node either has no children, or was reported in the correct order.
			if !(start == end || end == size) {
				b.err = fmt.Errorf("%v parser error: out of order nodes for declarative AST: %v, %v, %v", b.lang, t, startOffset, endOffset)
			}
			// Remove the node's subtree from the buffer.
			b.buffer = b.buffer[:se.subtreeIdx]
			// Remove the node's children from the stack.
			copy(b.stack[start:], b.stack[end:])
			b.stack = b.stack[:size-(end-start)]
			// Forget all texts that are stored after subtreeIdx.
			for i := len(b.texts) - 1; i >= 0; i-- {
				if e := b.texts[i]; e.index >= se.subtreeIdx {
					delete(b.textMap, e.text)
					b.texts = b.texts[:i]
				} else {
					break
				}
			}
			return
		}

		// For nodes that retain their text in declarative ASTs, store their text in buffer.
		for i := start; i < end; i++ {
			child := &b.stack[i]
			if child.t.HasProperty(node.RetainsText) {
				text := b.source[child.r.Offset:child.r.EndOffset]
				index := 0
				if j := b.textMap[text]; j > 0 {
					// Text is already stored, reuse index.
					index = j
				} else {
					// Store the text in the buffer, update mapping.
					index = b.packText(text)
					b.texts = append(b.texts, textElem{index, text})
					b.textMap[text] = index
				}
				child.textIdx = index
			}
		}
	}

	if start < end {
		se.firstChildIdx = len(b.buffer)
	}

	// Consume all nodes in the range [start,end).
	prev := 0
	for i := start; i < end; i++ {
		prev = b.addNodeToBuffer(&b.stack[i], prev)
	}
	if end == size {
		// Children are on top of the stack.
		b.stack = append(b.stack[:start], se)
	} else if start < end {
		// Children are within the stack.
		b.stack[start] = se
		copy(b.stack[start+1:], b.stack[end:])
		b.stack = b.stack[:size-(end-start-1)]
	} else {
		// No children.
		b.stack = append(b.stack, stackElem{})
		copy(b.stack[start+1:], b.stack[start:])
		b.stack[start] = se
	}
}

// tree returns the tree constructed by the builder.
func (b *builder) tree() *Tree {
	if len(b.stack) != 1 {
		// The parser failed to produce exactly one node, adding one.
		b.addNode(node.BrokenFile, 0, len(b.source))
	}

	// Add root to buffer.
	index := b.addNodeToBuffer(&b.stack[0], 0)
	// The root has no parent.
	b.setParents(index, 0)
	// Add size of the root node to the buffer.
	b.buffer = append(b.buffer, byte(len(b.buffer)-index))

	return &Tree{
		buffer: b.buffer,
		lang:   b.lang,
		path:   b.path,
		source: b.source,
		mapper: offset.NewMapper(b.source),
		t:      b.opts.Type,
	}
}

func newBuilder(lang lpb.Language, path, source string, opts Options) *builder {
	buffer := make([]byte, 0, 1024)
	buffer = append(buffer, formatVersion, byte(opts.Type), 0, 0)
	binary.LittleEndian.PutUint16(buffer[2:], uint16(lang))
	return &builder{
		lang:    lang,
		opts:    opts,
		path:    path,
		source:  source,
		buffer:  buffer,
		stack:   make([]stackElem, 0, 1024),
		textMap: make(map[string]int),
	}
}

// Build produces an AST for the input source, built by the parser registered for the language.
// Returns a half-constructed tree with BrokenFile as the root, and an error if "source" cannot be
// parsed.
func Build(ctx context.Context, l lpb.Language, path, source string, opts Options) (*Tree, error) {
	builder := newBuilder(l, path, source, opts)
	err := parsers.Parse(ctx, l, source, builder.addNode, parsers.Options{
		IncludeAllTokens:   opts.IncludeAllTokens,
		ShouldTryToRecover: opts.ShouldTryToRecover,
	})
	if err == parsers.ErrUnsupportedLanguage {
		return nil, err
	}
	if err == nil {
		err = builder.err
	}
	if err != nil {
		builder.addNode(node.BrokenFile, 0, len(source))
	}
	return builder.tree(), err
}

// FromBytes returns a Tree backed by the provided bytes, or an error if it couldn't be created.
// For full ASTs, if the source is not provided, Text() will return an empty string for all nodes.
func FromBytes(bytes []byte, path, source string) (*Tree, error) {
	if len(bytes) < firstNodeOffset+offsetOrTextPos+1 {
		return nil, errTooSmall
	}

	if bytes[0] != formatVersion {
		return nil, errWrongFormat
	}

	return &Tree{
		buffer: bytes,
		t:      Type(bytes[1]),
		path:   path,
		source: source,
		lang:   lpb.Language(binary.LittleEndian.Uint16(bytes[2:])),
	}, nil
}
