// Licensed to Apache Software Foundation (ASF) under one or more contributor
// license agreements. See the NOTICE file distributed with
// this work for additional information regarding copyright
// ownership. Apache Software Foundation (ASF) licenses this file to you 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 trace

import (
	"bytes"
	"fmt"
	"maps"
	"sort"

	"github.com/apache/skywalking-banyandb/pkg/convert"
	"github.com/apache/skywalking-banyandb/pkg/encoding"
	pbv1 "github.com/apache/skywalking-banyandb/pkg/pb/v1"
	"github.com/apache/skywalking-banyandb/pkg/pool"
	"github.com/apache/skywalking-banyandb/pkg/query/model"
)

type dataBlock struct {
	offset uint64
	size   uint64
}

func (d *dataBlock) reset() {
	d.offset = 0
	d.size = 0
}

func (d *dataBlock) copyFrom(src *dataBlock) {
	d.offset = src.offset
	d.size = src.size
}

func (d *dataBlock) marshal(dst []byte) []byte {
	dst = encoding.VarUint64ToBytes(dst, d.offset)
	dst = encoding.VarUint64ToBytes(dst, d.size)
	return dst
}

func (d *dataBlock) unmarshal(src []byte) []byte {
	src, n := encoding.BytesToVarUint64(src)
	d.offset = n

	src, n = encoding.BytesToVarUint64(src)
	d.size = n
	return src
}

type blockMetadata struct {
	tags                      map[string]*dataBlock
	tagType                   map[string]pbv1.ValueType
	spans                     *dataBlock
	tagProjection             *model.TagProjection
	traceID                   string
	timestamps                timestampsMetadata
	uncompressedSpanSizeBytes uint64
	count                     uint64
}

func (bm *blockMetadata) copyFrom(src *blockMetadata) {
	bm.traceID = src.traceID
	bm.uncompressedSpanSizeBytes = src.uncompressedSpanSizeBytes
	bm.count = src.count
	if bm.spans == nil {
		bm.spans = &dataBlock{}
	}
	bm.spans.copyFrom(src.spans)
	bm.timestamps.copyFrom(&src.timestamps)
	for k, db := range src.tags {
		if bm.tags == nil {
			bm.tags = make(map[string]*dataBlock)
		}
		bm.tags[k] = &dataBlock{}
		bm.tags[k].copyFrom(db)
	}
	for k, vt := range src.tagType {
		if bm.tagType == nil {
			bm.tagType = make(map[string]pbv1.ValueType)
		}
		bm.tagType[k] = vt
	}
}

func (bm *blockMetadata) getTagMetadata(name string) *dataBlock {
	if bm.tags == nil {
		bm.tags = make(map[string]*dataBlock)
	}
	t, ok := bm.tags[name]
	if !ok {
		t = &dataBlock{}
		bm.tags[name] = t
	}
	return t
}

func (bm *blockMetadata) reset() {
	bm.traceID = ""
	bm.uncompressedSpanSizeBytes = 0
	bm.count = 0
	bm.tagProjection = nil
	if bm.spans == nil {
		bm.spans = &dataBlock{}
	} else {
		bm.spans.reset()
	}
	bm.timestamps.reset()
	if bm.tags == nil {
		bm.tags = make(map[string]*dataBlock)
	} else {
		for k := range bm.tags {
			bm.tags[k].reset()
			delete(bm.tags, k)
		}
	}
	if bm.tagType == nil {
		bm.tagType = make(map[string]pbv1.ValueType)
	} else {
		for k := range bm.tagType {
			delete(bm.tagType, k)
		}
	}
}

func (bm *blockMetadata) marshal(dst []byte) []byte {
	dst = encoding.EncodeBytes(dst, convert.StringToBytes(bm.traceID))
	dst = encoding.VarUint64ToBytes(dst, bm.uncompressedSpanSizeBytes)
	dst = encoding.VarUint64ToBytes(dst, bm.count)
	knownMarker := uint64(0)
	if bm.timestamps.known {
		knownMarker = 1
	}
	dst = encoding.VarUint64ToBytes(dst, knownMarker)
	dst = encoding.VarInt64ToBytes(dst, bm.timestamps.min)
	dst = encoding.VarInt64ToBytes(dst, bm.timestamps.max)
	dst = bm.spans.marshal(dst)
	dst = encoding.VarUint64ToBytes(dst, uint64(len(bm.tags)))
	// make sure the order of tags is stable
	keys := make([]string, 0, len(bm.tags))
	for k := range bm.tags {
		keys = append(keys, k)
	}
	sort.Strings(keys)
	for _, name := range keys {
		t := bm.tags[name]
		dst = encoding.EncodeBytes(dst, convert.StringToBytes(name))
		dst = t.marshal(dst)
	}
	return dst
}

func (bm *blockMetadata) unmarshal(src []byte, tagType map[string]pbv1.ValueType) ([]byte, error) {
	src, traceIDBytes, err := encoding.DecodeBytes(src)
	if err != nil {
		return nil, fmt.Errorf("cannot unmarshal traceID: %w", err)
	}
	bm.traceID = string(traceIDBytes)
	if bm.tagType == nil {
		bm.tagType = make(map[string]pbv1.ValueType)
	} else {
		clear(bm.tagType)
	}
	maps.Copy(bm.tagType, tagType)
	src, n := encoding.BytesToVarUint64(src)
	bm.uncompressedSpanSizeBytes = n
	src, n = encoding.BytesToVarUint64(src)
	bm.count = n
	src, n = encoding.BytesToVarUint64(src)
	if n > 1 {
		return nil, fmt.Errorf("cannot unmarshal timestamp bounds marker: %d", n)
	}
	bm.timestamps.known = n == 1
	var timestampErr error
	src, bm.timestamps.min, timestampErr = encoding.BytesToVarInt64(src)
	if timestampErr != nil {
		return nil, fmt.Errorf("cannot unmarshal minimum timestamp: %w", timestampErr)
	}
	src, bm.timestamps.max, timestampErr = encoding.BytesToVarInt64(src)
	if timestampErr != nil {
		return nil, fmt.Errorf("cannot unmarshal maximum timestamp: %w", timestampErr)
	}
	if bm.spans == nil {
		bm.spans = &dataBlock{}
	}
	src = bm.spans.unmarshal(src)

	src, n = encoding.BytesToVarUint64(src)
	if n > 0 {
		if bm.tags == nil {
			bm.tags = make(map[string]*dataBlock, n)
		}
		var nameBytes []byte
		var err error
		for i := uint64(0); i < n; i++ {
			src, nameBytes, err = encoding.DecodeBytes(src)
			if err != nil {
				return nil, fmt.Errorf("cannot unmarshal tag name: %w", err)
			}
			t := &dataBlock{}
			src = t.unmarshal(src)
			bm.tags[string(nameBytes)] = t
		}
	}
	return src, nil
}

func (bm *blockMetadata) less(other *blockMetadata) bool {
	return bm.traceID < other.traceID
}

func generateBlockMetadata() *blockMetadata {
	v := blockMetadataPool.Get()
	if v == nil {
		return &blockMetadata{}
	}
	return v
}

func releaseBlockMetadata(bm *blockMetadata) {
	bm.reset()
	blockMetadataPool.Put(bm)
}

var blockMetadataPool = pool.Register[*blockMetadata]("trace-blockMetadata")

type blockMetadataArray struct {
	arr []blockMetadata
}

func (bma *blockMetadataArray) reset() {
	for i := range bma.arr {
		bma.arr[i].reset()
	}
	bma.arr = bma.arr[:0]
}

var blockMetadataArrayPool = pool.Register[*blockMetadataArray]("trace-blockMetadataArray")

func generateBlockMetadataArray() *blockMetadataArray {
	v := blockMetadataArrayPool.Get()
	if v == nil {
		return &blockMetadataArray{}
	}
	return v
}

func releaseBlockMetadataArray(bma *blockMetadataArray) {
	bma.reset()
	blockMetadataArrayPool.Put(bma)
}

type timestampsMetadata struct {
	min   int64
	max   int64
	known bool
}

func (tm *timestampsMetadata) reset() {
	tm.min = 0
	tm.max = 0
	tm.known = false
}

func (tm *timestampsMetadata) copyFrom(src *timestampsMetadata) {
	tm.min = src.min
	tm.max = src.max
	tm.known = src.known
}

func unmarshalBlockMetadata(dst []blockMetadata, src []byte, tagType map[string]pbv1.ValueType) ([]blockMetadata, error) {
	dstOrig := dst
	var pre *blockMetadata
	for len(src) > 0 {
		if len(dst) < cap(dst) {
			dst = dst[:len(dst)+1]
		} else {
			dst = append(dst, blockMetadata{})
		}
		bm := &dst[len(dst)-1]
		bm.reset()
		tail, err := bm.unmarshal(src, tagType)
		if err != nil {
			return dstOrig, fmt.Errorf("cannot unmarshal blockMetadata entries: %w", err)
		}
		src = tail

		// Validate the order of blockMetadata during unmarshalling
		if pre != nil {
			if err := validateBlockMetadataOrder(pre, bm); err != nil {
				return dstOrig, err
			}
		}
		pre = bm
	}
	return dst, nil
}

// skipBlockMetadataAfterTraceID advances src — positioned immediately after a
// blockMetadata entry's traceID — past the entry's remaining fields without allocating
// its tag map. It mirrors the field order of blockMetadata.marshal after the traceID, so
// it consumes precisely the rest of one entry.
func skipBlockMetadataAfterTraceID(src []byte) ([]byte, error) {
	src, _ = encoding.BytesToVarUint64(src) // uncompressedSpanSizeBytes
	src, _ = encoding.BytesToVarUint64(src) // count
	src, knownMarker := encoding.BytesToVarUint64(src)
	if knownMarker > 1 {
		return nil, fmt.Errorf("cannot skip timestamp bounds marker: %d", knownMarker)
	}
	var timestampErr error
	src, _, timestampErr = encoding.BytesToVarInt64(src) // timestamps.min
	if timestampErr != nil {
		return nil, fmt.Errorf("cannot skip minimum timestamp: %w", timestampErr)
	}
	src, _, timestampErr = encoding.BytesToVarInt64(src) // timestamps.max
	if timestampErr != nil {
		return nil, fmt.Errorf("cannot skip maximum timestamp: %w", timestampErr)
	}
	src, _ = encoding.BytesToVarUint64(src) // spans.offset
	src, _ = encoding.BytesToVarUint64(src) // spans.size
	var tagCount uint64
	src, tagCount = encoding.BytesToVarUint64(src)
	for i := uint64(0); i < tagCount; i++ {
		var err error
		src, _, err = encoding.DecodeBytes(src) // tag name
		if err != nil {
			return nil, fmt.Errorf("cannot skip tag name: %w", err)
		}
		src, _ = encoding.BytesToVarUint64(src) // dataBlock.offset
		src, _ = encoding.BytesToVarUint64(src) // dataBlock.size
	}
	return src, nil
}

// unmarshalBlockMetadataFiltered decodes only the blockMetadata entries in src whose
// traceID appears in wanted, cheaply skipping the rest. Both the src entries and wanted
// are sorted by traceID, so a single merge-walk over them suffices. The result is
// equivalent to filtering unmarshalBlockMetadata's output to entries whose traceID is in
// wanted, but it avoids building the tag map for skipped entries — the dominant cost when
// only a few of the granule's entries are requested (e.g. a trace-id point lookup). Each
// entry's traceID is decoded once up front to decide; matched entries are then fully
// decoded, so the overhead on a full scan (every entry matched) is one extra traceID
// decode per entry and no extra allocation.
func unmarshalBlockMetadataFiltered(dst []blockMetadata, src []byte, tagType map[string]pbv1.ValueType, wanted []string) ([]blockMetadata, error) {
	dstOrig := dst
	wantIdx := 0
	var pre *blockMetadata
	for len(src) > 0 && wantIdx < len(wanted) {
		rest, traceID, err := encoding.DecodeBytes(src)
		if err != nil {
			return dstOrig, fmt.Errorf("cannot unmarshal traceID: %w", err)
		}
		for wantIdx < len(wanted) && bytes.Compare(convert.StringToBytes(wanted[wantIdx]), traceID) < 0 {
			wantIdx++
		}
		if wantIdx < len(wanted) && bytes.Equal(convert.StringToBytes(wanted[wantIdx]), traceID) {
			if len(dst) < cap(dst) {
				dst = dst[:len(dst)+1]
			} else {
				dst = append(dst, blockMetadata{})
			}
			bm := &dst[len(dst)-1]
			bm.reset()
			tail, uErr := bm.unmarshal(src, tagType)
			if uErr != nil {
				return dstOrig, fmt.Errorf("cannot unmarshal blockMetadata entries: %w", uErr)
			}
			if pre != nil {
				if vErr := validateBlockMetadataOrder(pre, bm); vErr != nil {
					return dstOrig, vErr
				}
			}
			pre = bm
			src = tail
			continue
		}
		tail, sErr := skipBlockMetadataAfterTraceID(rest)
		if sErr != nil {
			return dstOrig, fmt.Errorf("cannot skip blockMetadata entry: %w", sErr)
		}
		src = tail
	}
	return dst, nil
}

func validateBlockMetadataOrder(pre, cur *blockMetadata) error {
	if cur.traceID < pre.traceID {
		return fmt.Errorf("unexpected blockMetadata with smaller traceID=%s after bigger traceID=%s", cur.traceID, pre.traceID)
	}
	return nil
}
