package tokenanalysis

import (
	"bytes"
	"crypto/sha256"
	"encoding/hex"
	"encoding/json"
	"errors"
	"fmt"
	"io"
	"math"
	"math/bits"
	"os"
	"sort"
	"strings"

	"github.com/tidbcloud/AgentTeam/desktop/internal/metrics"
)

const MaxArtifactBytes = 1 << 20

type Comparison struct {
	SchemaVersion        string       `json:"schemaVersion"`
	State                string       `json:"state"`
	MismatchReasons      []string     `json:"mismatchReasons"`
	BaselineFingerprint  string       `json:"baselineFingerprint"`
	CandidateFingerprint string       `json:"candidateFingerprint"`
	InputDelta           int64        `json:"inputDelta"`
	InputRatio           *float64     `json:"inputRatio,omitempty"`
	RootInvocationDelta  *int64       `json:"rootInvocationDelta,omitempty"`
	ControllableDelta    *int64       `json:"controllableDelta,omitempty"`
	UncachedInputDelta   *int64       `json:"uncachedInputDelta,omitempty"`
	CacheReadDelta       *int64       `json:"cacheReadDelta,omitempty"`
	BlockDeltas          []BlockDelta `json:"blockDeltas"`
	LedgerState          string       `json:"ledgerState"`
	Note                 string       `json:"note"`
}

type BlockDelta struct {
	BlockID         string `json:"blockId"`
	DisplayName     string `json:"displayName"`
	BaselineTokens  uint64 `json:"baselineTokens"`
	CandidateTokens uint64 `json:"candidateTokens"`
	DeltaTokens     int64  `json:"deltaTokens"`
}

func Compare(baseline, candidate Report) Comparison {
	state, reasons := comparisonState(baseline, candidate)
	out := Comparison{
		SchemaVersion:        ComparisonSchemaVersion,
		State:                state,
		MismatchReasons:      reasons,
		BaselineFingerprint:  baseline.Fingerprint,
		CandidateFingerprint: candidate.Fingerprint,
		BlockDeltas:          []BlockDelta{},
		LedgerState:          StateAvailable,
		Note:                 "Differences are diagnostic evidence, not an automatic causal or savings verdict.",
	}
	if state == "not_comparable" {
		return out
	}
	out.InputDelta = signedDelta(baseline.Summary.RuntimeInput, candidate.Summary.RuntimeInput)
	out.InputRatio = ratioPtr(candidate.Summary.RuntimeInput, baseline.Summary.RuntimeInput)
	if baseline.Summary.RuntimeCacheRead <= baseline.Summary.RuntimeInput &&
		candidate.Summary.RuntimeCacheRead <= candidate.Summary.RuntimeInput {
		value := signedDelta(
			baseline.Summary.RuntimeInput-baseline.Summary.RuntimeCacheRead,
			candidate.Summary.RuntimeInput-candidate.Summary.RuntimeCacheRead,
		)
		out.UncachedInputDelta = &value
	}
	cacheDelta := signedDelta(baseline.Summary.RuntimeCacheRead, candidate.Summary.RuntimeCacheRead)
	out.CacheReadDelta = &cacheDelta
	if before, after, ok := metricPair(baseline.Summary.RootModelInvocations, candidate.Summary.RootModelInvocations); ok {
		value := signedDelta(before, after)
		out.RootInvocationDelta = &value
	}
	if before, after, ok := metricPair(baseline.Summary.ControllableMaterialized, candidate.Summary.ControllableMaterialized); ok {
		value := signedDelta(before, after)
		out.ControllableDelta = &value
	}
	if baseline.DataQuality.Truncated || candidate.DataQuality.Truncated {
		out.LedgerState = StateLimited
		return out
	}
	beforeByID := make(map[string]BlockSummary, len(baseline.Ledger))
	afterByID := make(map[string]BlockSummary, len(candidate.Ledger))
	ids := make(map[string]struct{}, len(baseline.Ledger)+len(candidate.Ledger))
	for _, block := range baseline.Ledger {
		beforeByID[block.BlockID] = block
		ids[block.BlockID] = struct{}{}
	}
	for _, block := range candidate.Ledger {
		afterByID[block.BlockID] = block
		ids[block.BlockID] = struct{}{}
	}
	for id := range ids {
		before, after := beforeByID[id], afterByID[id]
		out.BlockDeltas = append(out.BlockDeltas, BlockDelta{
			BlockID:         id,
			DisplayName:     metadataFor(id, "").DisplayName,
			BaselineTokens:  before.MaterializedEstimate,
			CandidateTokens: after.MaterializedEstimate,
			DeltaTokens:     signedDelta(before.MaterializedEstimate, after.MaterializedEstimate),
		})
	}
	sort.Slice(out.BlockDeltas, func(i, j int) bool {
		left := math.Abs(float64(out.BlockDeltas[i].DeltaTokens))
		right := math.Abs(float64(out.BlockDeltas[j].DeltaTokens))
		if left != right {
			return left > right
		}
		return out.BlockDeltas[i].BlockID < out.BlockDeltas[j].BlockID
	})
	return out
}

func ReadReport(path string) (Report, error) {
	file, err := os.Open(path)
	if err != nil {
		return Report{}, fmt.Errorf("read token report: %w", err)
	}
	defer file.Close()
	data, err := io.ReadAll(io.LimitReader(file, MaxArtifactBytes+1))
	if err != nil {
		return Report{}, fmt.Errorf("read token report: %w", err)
	}
	if len(data) > MaxArtifactBytes {
		return Report{}, fmt.Errorf("token report exceeds %d bytes", MaxArtifactBytes)
	}
	var report Report
	decoder := json.NewDecoder(bytes.NewReader(data))
	decoder.DisallowUnknownFields()
	if err := decoder.Decode(&report); err != nil {
		return Report{}, fmt.Errorf("decode token report: %w", err)
	}
	var extra any
	if err := decoder.Decode(&extra); !errors.Is(err, io.EOF) {
		return Report{}, errors.New("token report must contain one JSON value")
	}
	if err := ValidatePortableReport(report); err != nil {
		return Report{}, err
	}
	return report, nil
}

func ValidateReport(report Report) error {
	if err := validateReportEnvelope(report); err != nil {
		return err
	}
	if err := validateReportSummary(report); err != nil {
		return err
	}
	ledgerByID := make(map[string]BlockSummary, len(report.Ledger))
	for _, block := range report.Ledger {
		if err := validateBlockSummary(block); err != nil {
			return err
		}
		if _, duplicate := ledgerByID[block.BlockID]; duplicate {
			return errors.New("token report contains duplicate block identity")
		}
		ledgerByID[block.BlockID] = block
	}
	opportunityIDs := make(map[string]struct{}, len(report.Opportunities))
	for _, opportunity := range report.Opportunities {
		if _, duplicate := opportunityIDs[opportunity.BlockID]; duplicate {
			return errors.New("token report contains duplicate opportunity identity")
		}
		opportunityIDs[opportunity.BlockID] = struct{}{}
		if err := validateOpportunity(opportunity, ledgerByID[opportunity.BlockID]); err != nil {
			return err
		}
	}
	for _, agent := range report.Agents {
		if !validOpaqueRef(agent.AgentRef, "agent") ||
			len(agent.DisplayName) > 256 ||
			len(agent.Runtime) > 128 || len(agent.Model) > 256 {
			return errors.New("token report contains oversized Agent metadata")
		}
	}
	for _, run := range report.Runs {
		if !validOpaqueRef(run.RunRef, "run") ||
			!validOpaqueRef(run.AgentRef, "agent") ||
			run.Kind != "root" ||
			len(run.Runtime) > 128 || len(run.Model) > 256 ||
			!validMetricValue(run.ModelInvocations) ||
			!validMetricValue(run.AverageInputPerInvocation) ||
			!validMetricValue(run.CompiledMaterialized) ||
			!validMetricValue(run.ControllableMaterialized) ||
			!validMetricValue(run.ControllableExposure) ||
			!validMetricValue(run.RequiredPayloadMaterialized) {
			return errors.New("token report contains invalid Run metadata")
		}
	}
	return nil
}

func validateReportEnvelope(report Report) error {
	if report.SchemaVersion != AnalysisSchemaVersion {
		return fmt.Errorf("unsupported token report schema %q", report.SchemaVersion)
	}
	if report.GeneratedAt.IsZero() ||
		report.SnapshotAt.IsZero() ||
		len(report.Window) > 3 ||
		len(report.DataQuality.Diagnostics) > 64 ||
		len(report.Comparability.CaseFingerprint) > 128 ||
		len(report.Comparability.RuntimeFingerprint) > 128 ||
		len(report.Comparability.BuildFingerprint) > 128 ||
		len(report.Comparability.WorkspaceFingerprint) > 128 ||
		len(report.Comparability.ToolFingerprint) > 128 ||
		len(report.Comparability.TaskPayloadFingerprint) > 128 ||
		(report.Comparability.TaskPayloadFingerprint != "" && !lowerHexFingerprint(report.Comparability.TaskPayloadFingerprint)) ||
		len(report.Comparability.ChangedVariable) > 128 ||
		len(report.Comparability.ScopeFingerprint) > 128 {
		return errors.New("token report contains invalid metadata")
	}
	if report.SnapshotAt.After(report.GeneratedAt) {
		return errors.New("token report contains invalid snapshot boundary")
	}
	if _, err := ParseWindow(report.Window); err != nil {
		return err
	}
	if (report.Scope.Kind != "all_agents" && report.Scope.Kind != "agent" && report.Scope.Kind != "run") ||
		(report.Scope.RunState != "not_applicable" && report.Scope.RunState != "active" && report.Scope.RunState != "ended") ||
		(report.Scope.Kind == "run" && report.Scope.RunState == "not_applicable") ||
		(report.Scope.Kind != "run" && report.Scope.RunState != "not_applicable") {
		return errors.New("token report contains invalid analysis scope")
	}
	if report.DataQuality.Scanned < 0 || report.DataQuality.Limit < 0 ||
		report.DataQuality.Scanned > report.DataQuality.Limit ||
		report.DataQuality.Limit > metrics.MaxTokenEvidenceSamples ||
		!validComparabilityValue(report.Comparability.CacheState, "cold", "warm", "unknown") ||
		!validComparabilityValue(report.Comparability.Outcome, "success", "failure", "unknown") {
		return errors.New("token report contains invalid data-quality metadata")
	}
	for _, diagnostic := range report.DataQuality.Diagnostics {
		if len(diagnostic) == 0 || len(diagnostic) > 128 {
			return errors.New("token report contains invalid diagnostic")
		}
	}
	if len(report.Agents) > 512 || len(report.Runs) > 4096 || len(report.Ledger) > maxReportLedger || len(report.Opportunities) > 12 {
		return errors.New("token report exceeds collection bounds")
	}
	if len(report.Fingerprint) != 16 {
		return errors.New("invalid token report fingerprint")
	}
	if report.Fingerprint != reportFingerprint(report) {
		return errors.New("token report fingerprint does not match its evidence")
	}
	return nil
}

func lowerHexFingerprint(value string) bool {
	if len(value) != 32 {
		return false
	}
	for _, char := range value {
		if (char < '0' || char > '9') && (char < 'a' || char > 'f') {
			return false
		}
	}
	return true
}

func validateReportSummary(report Report) error {
	if report.Summary.RuntimeCacheRead > report.Summary.RuntimeInput {
		return errors.New("token report contains invalid cache-read total")
	}
	if !validMetricValue(report.Summary.RootModelInvocations) ||
		!validMetricValue(report.Summary.RootAverageInputPerInvocation) ||
		!validMetricValue(report.Summary.RootRuntimeInput) ||
		!validMetricValue(report.Summary.UnattributedInput) ||
		!validMetricValue(report.Summary.CompiledMaterialized) ||
		!validMetricValue(report.Summary.ControllableMaterialized) ||
		!validMetricValue(report.Summary.ControllableExposure) ||
		!validMetricValue(report.Summary.RequiredPayload) ||
		!validMetricValue(report.Summary.ContextPartition.AgentTeamOwned) ||
		!validMetricValue(report.Summary.ContextPartition.WorkspaceConfiguration) ||
		!validMetricValue(report.Summary.ContextPartition.UserTaskPayload) ||
		!validMetricValue(report.Summary.ContextPartition.Unknown) ||
		!validDataState(report.DataQuality.State) {
		return errors.New("token report contains invalid metric state")
	}
	if compiled, agentteamOwned, workspace, task, unknown, ok := contextPartitionValues(report.Summary); ok {
		total, firstCarry := bits.Add64(agentteamOwned, workspace, 0)
		total, secondCarry := bits.Add64(total, task, 0)
		total, thirdCarry := bits.Add64(total, unknown, 0)
		if firstCarry|secondCarry|thirdCarry != 0 || compiled != total {
			return errors.New("token report contains overlapping Context partition")
		}
	}
	return nil
}

func validateBlockSummary(block BlockSummary) error {
	if safeBlockID(block.BlockID) != block.BlockID {
		return errors.New("token report contains unknown block identity")
	}
	if !validOrigin(block.Origin) || !validControl(block.Control) || !validLifetime(block.Lifetime) {
		return errors.New("token report contains invalid block classification")
	}
	metadata := metadataFor(block.BlockID, "")
	if block.DisplayName != metadata.DisplayName ||
		block.Origin != metadata.Origin ||
		block.Control != metadata.Control ||
		block.SuggestedAction != metadata.SuggestedAction ||
		!equalStrings(block.RequiredValidation, metadata.Validation) {
		return errors.New("token report contains non-resolved block metadata")
	}
	if !finiteNonNegative(block.MeanWhenInjected) ||
		!finiteUnit(block.InjectionCoverage) ||
		len(block.DisplayName) > 160 ||
		len(block.SuggestedAction) > 1024 ||
		len(block.RequiredValidation) > 32 {
		return errors.New("token report contains invalid block values")
	}
	if eligibleControl(metadata) &&
		(block.ExposureEstimate == nil) != (block.ControllableExposure == nil) {
		return errors.New("token report contains inconsistent exposure estimate")
	}
	if !eligibleControl(metadata) && block.ControllableExposure != nil {
		return errors.New("token report contains ineligible controllable exposure")
	}
	if block.ExposureEstimate == nil && block.ExposureCount != 0 {
		return errors.New("token report contains exposure count without estimate")
	}
	if block.ControllableExposure != nil &&
		(block.ExposureEstimate == nil || *block.ControllableExposure > *block.ExposureEstimate) {
		return errors.New("token report contains invalid controllable exposure")
	}
	if metadata.TargetPerInjection == nil {
		if block.AddressableEstimate != nil {
			return errors.New("token report contains addressable estimate without target")
		}
		return nil
	}
	if block.ExposureEstimate == nil {
		if block.AddressableEstimate != nil {
			return errors.New("token report contains addressable estimate without exposure")
		}
		return nil
	}
	expected := saturatingSubtract(
		*block.ExposureEstimate,
		saturatingMultiply(*metadata.TargetPerInjection, block.ExposureCount),
	)
	if block.AddressableEstimate == nil || *block.AddressableEstimate != expected {
		return errors.New("token report contains invalid addressable estimate")
	}
	return nil
}

func validateOpportunity(opportunity Opportunity, block BlockSummary) error {
	if safeBlockID(opportunity.BlockID) != opportunity.BlockID ||
		!validOrigin(opportunity.Origin) ||
		!validControl(opportunity.Control) ||
		len(opportunity.DisplayName) > 160 ||
		len(opportunity.SuggestedAction) > 1024 ||
		len(opportunity.RequiredValidation) > 32 {
		return errors.New("token report contains invalid opportunity")
	}
	metadata := metadataFor(opportunity.BlockID, "")
	expected := block.MaterializedEstimate
	estimator := "materialized_contribution"
	if block.ControllableExposure != nil {
		expected = *block.ControllableExposure
		estimator = "exposure_contribution"
	}
	if block.AddressableEstimate != nil {
		expected = *block.AddressableEstimate
		estimator = "addressable_exposure_target"
	}
	if opportunity.Estimate == 0 ||
		opportunity.Estimate != expected ||
		opportunity.Estimator != estimator {
		return errors.New("token report contains invalid opportunity estimator")
	}
	if opportunity.DisplayName != metadata.DisplayName ||
		opportunity.Origin != metadata.Origin ||
		opportunity.Control != metadata.Control ||
		opportunity.SuggestedAction != metadata.SuggestedAction ||
		!equalStrings(opportunity.RequiredValidation, metadata.Validation) {
		return errors.New("token report contains non-canonical opportunity metadata")
	}
	return nil
}

func ValidatePortableReport(report Report) error {
	if err := ValidateReport(report); err != nil {
		return err
	}
	if len(report.Agents) != 0 || len(report.Runs) != 0 {
		return errors.New("portable token report contains machine-local Agent or Run references")
	}
	return nil
}

// Portable removes machine-local Agent/Run detail and exact runtime/model
// values while retaining stable aggregate evidence.
func Portable(report Report) Report {
	portable := report
	runtimeValues := make(map[string]struct{})
	for i := range portable.Agents {
		runtimeValues[portable.Agents[i].Runtime+"\x00"+portable.Agents[i].Model] = struct{}{}
		portable.Agents[i].DisplayName = ""
		portable.Agents[i].Runtime = ""
		portable.Agents[i].Model = ""
	}
	for i := range portable.Runs {
		runtimeValues[portable.Runs[i].Runtime+"\x00"+portable.Runs[i].Model] = struct{}{}
		portable.Runs[i].Runtime = ""
		portable.Runs[i].Model = ""
	}
	portable.Agents = []AgentSummary{}
	portable.Runs = []RunSummary{}
	delete(runtimeValues, "\x00")
	if portable.Comparability.RuntimeFingerprint == "" {
		if len(runtimeValues) > 0 {
			values := make([]string, 0, len(runtimeValues))
			for value := range runtimeValues {
				values = append(values, value)
			}
			sort.Strings(values)
			runtimeHash := sha256.New()
			for _, value := range values {
				_, _ = runtimeHash.Write([]byte(value))
				_, _ = runtimeHash.Write([]byte{0})
			}
			portable.Comparability.RuntimeFingerprint = hex.EncodeToString(runtimeHash.Sum(nil))[:16]
		}
	}
	portable.Fingerprint = reportFingerprint(portable)
	return portable
}

func comparisonState(baseline, candidate Report) (string, []string) {
	type value struct {
		name   string
		before string
		after  string
	}
	values := []value{
		{"case", baseline.Comparability.CaseFingerprint, candidate.Comparability.CaseFingerprint},
		{"runtime", baseline.Comparability.RuntimeFingerprint, candidate.Comparability.RuntimeFingerprint},
		{"workspace", baseline.Comparability.WorkspaceFingerprint, candidate.Comparability.WorkspaceFingerprint},
		{"tools", baseline.Comparability.ToolFingerprint, candidate.Comparability.ToolFingerprint},
		{"task_payload", baseline.Comparability.TaskPayloadFingerprint, candidate.Comparability.TaskPayloadFingerprint},
		{"scope", baseline.Comparability.ScopeFingerprint, candidate.Comparability.ScopeFingerprint},
		{"changed_variable", baseline.Comparability.ChangedVariable, candidate.Comparability.ChangedVariable},
	}
	var missing bool
	declaredChange := strings.TrimSpace(baseline.Comparability.ChangedVariable) != "" &&
		baseline.Comparability.ChangedVariable == candidate.Comparability.ChangedVariable
	if !declaredChange {
		values = append(values, value{
			"build",
			baseline.Comparability.BuildFingerprint,
			candidate.Comparability.BuildFingerprint,
		})
	} else if strings.TrimSpace(baseline.Comparability.BuildFingerprint) == "" ||
		strings.TrimSpace(candidate.Comparability.BuildFingerprint) == "" {
		missing = true
	}
	var mismatch []string
	for _, item := range values {
		if strings.TrimSpace(item.before) == "" || strings.TrimSpace(item.after) == "" {
			missing = true
			continue
		}
		if item.before != item.after {
			mismatch = append(mismatch, item.name+"_mismatch")
		}
	}
	if declaredChange && (baseline.Scope.Kind != "run" || candidate.Scope.Kind != "run") {
		mismatch = append(mismatch, "run_scope_required")
	}
	if baseline.Comparability.CacheState != candidate.Comparability.CacheState ||
		baseline.Comparability.Outcome != candidate.Comparability.Outcome {
		if baseline.Comparability.CacheState != candidate.Comparability.CacheState {
			mismatch = append(mismatch, "cache_state_mismatch")
		}
		if baseline.Comparability.Outcome != candidate.Comparability.Outcome {
			mismatch = append(mismatch, "outcome_mismatch")
		}
	}
	if baseline.Comparability.Outcome == "failure" || candidate.Comparability.Outcome == "failure" {
		mismatch = append(mismatch, "outcome_not_success")
	}
	if declaredChange &&
		(baseline.DataQuality.Truncated || candidate.DataQuality.Truncated ||
			baseline.DataQuality.State != StateAvailable ||
			candidate.DataQuality.State != StateAvailable) {
		mismatch = append(mismatch, "incomplete_evidence")
	}
	if len(mismatch) > 0 {
		return "not_comparable", mismatch
	}
	if strings.TrimSpace(baseline.Comparability.ChangedVariable) == "" ||
		strings.TrimSpace(candidate.Comparability.ChangedVariable) == "" {
		missing = true
	}
	if missing || baseline.Comparability.CacheState == "unknown" ||
		candidate.Comparability.CacheState == "unknown" ||
		baseline.Comparability.Outcome == "unknown" ||
		candidate.Comparability.Outcome == "unknown" {
		return "descriptive", []string{}
	}
	return "comparable", []string{}
}

func metricPair(before, after MetricValue) (uint64, uint64, bool) {
	if before.State != StateAvailable || after.State != StateAvailable || before.Value == nil || after.Value == nil {
		return 0, 0, false
	}
	return *before.Value, *after.Value, true
}

func contextPartitionValues(summary UsageSummary) (uint64, uint64, uint64, uint64, uint64, bool) {
	compiled, ok := metricValue(summary.CompiledMaterialized)
	if !ok {
		return 0, 0, 0, 0, 0, false
	}
	agentteamOwned, ok := metricValue(summary.ContextPartition.AgentTeamOwned)
	if !ok {
		return 0, 0, 0, 0, 0, false
	}
	workspace, ok := metricValue(summary.ContextPartition.WorkspaceConfiguration)
	if !ok {
		return 0, 0, 0, 0, 0, false
	}
	task, ok := metricValue(summary.ContextPartition.UserTaskPayload)
	if !ok {
		return 0, 0, 0, 0, 0, false
	}
	unknown, ok := metricValue(summary.ContextPartition.Unknown)
	return compiled, agentteamOwned, workspace, task, unknown, ok
}

func metricValue(value MetricValue) (uint64, bool) {
	if value.State != StateAvailable || value.Value == nil {
		return 0, false
	}
	return *value.Value, true
}

func signedDelta(before, after uint64) int64 {
	if after >= before {
		if after-before > math.MaxInt64 {
			return math.MaxInt64
		}
		return int64(after - before)
	}
	if before-after > math.MaxInt64 {
		return math.MinInt64
	}
	return -int64(before - after)
}

func ratioPtr(numerator, denominator uint64) *float64 {
	if denominator == 0 {
		return nil
	}
	value := float64(numerator) / float64(denominator)
	return &value
}

func validOrigin(value string) bool {
	switch value {
	case "agentteam_policy", "agentteam_generated", "workspace_configuration", "user_task_payload", "unknown":
		return true
	default:
		return false
	}
}

func validControl(value string) bool {
	switch value {
	case "direct", "assembly", "none", "unknown":
		return true
	default:
		return false
	}
}

func validLifetime(value string) bool {
	switch value {
	case "session_persistent", "boundary_only", "until_replaced", "unknown":
		return true
	default:
		return false
	}
}

func finiteNonNegative(value float64) bool {
	return !math.IsNaN(value) && !math.IsInf(value, 0) && value >= 0
}

func finiteUnit(value float64) bool {
	return finiteNonNegative(value) && value <= 1
}

func validMetricValue(value MetricValue) bool {
	if !validDataState(value.State) {
		return false
	}
	if value.State == StateAvailable {
		return value.Value != nil
	}
	return value.Value == nil
}

func validDataState(value string) bool {
	switch value {
	case StateAvailable, StateNoData, StateUnsupported, StateLimited, StateDisabled:
		return true
	default:
		return false
	}
}

func validComparabilityValue(value string, allowed ...string) bool {
	for _, candidate := range allowed {
		if value == candidate {
			return true
		}
	}
	return false
}

func validOpaqueRef(value, kind string) bool {
	prefix := kind + "_"
	if len(value) != len(prefix)+16 || !strings.HasPrefix(value, prefix) {
		return false
	}
	_, err := hex.DecodeString(strings.TrimPrefix(value, prefix))
	return err == nil
}

func equalStrings(left, right []string) bool {
	if len(left) != len(right) {
		return false
	}
	for index := range left {
		if left[index] != right[index] {
			return false
		}
	}
	return true
}