expression.go

package analysis

import (
	"cmp"
	"fmt"

	"github.com/ProCode-Software/klar/internal/ast"
	"github.com/ProCode-Software/klar/internal/klarerrs"
	"github.com/ProCode-Software/klar/internal/lexer"
	"github.com/ProCode-Software/klar/internal/ranges"
)

type Expr struct {
	Type    Type
	hint    Type
	mode    exprMode // Input mode
	gotMode exprMode // Output mode
	Root    *Expr
	Context *Context
	stmtCtx *stmtContext
}

func NewExpr(ctx *Context, flags ...exprMode) *Expr {
	e := &Expr{Context: ctx, mode: parseFlags(flags)}
	e.Root = e
	return e
}

func (e *Expr) NewChild(flags ...exprMode) *Expr {
	const noInherit = 0
	return &Expr{
		Context: e.Context,
		mode:    (e.mode &^ noInherit) | parseFlags(flags),
		stmtCtx: e.stmtCtx,
		Root:    e.Root,
	}
}

func (sctx *stmtContext) newExpr(flags ...exprMode) *Expr {
	e := &Expr{Context: sctx.ctx, mode: parseFlags(flags), stmtCtx: sctx}
	e.Root = e
	return e
}

// hint can be nil
func (e *Expr) withHint(hint Type) *Expr {
	e.hint = hint
	return e
}

func (e *Expr) withContext(ctx *Context) *Expr {
	e.Context = ctx
	return e
}

type exprMode uint16

const (
	// Input modes
	typeInit  exprMode = 1 << iota
	constExpr          // Can also be output
	exprStmt
	patternMatch
	indexLHS
	stringInterpolation
	allowNothingValue
	attributeFunc

	// Output modes
	todoExpr
	intfField
)

func (mode exprMode) has(opt exprMode) bool { return (mode & opt) != 0 }

func (e *Expr) ConstValue() ConstValue {
	return UnknownConst{}
}

func (e *Expr) Kind() Kind     { return e.Type.Kind() }
func (e *Expr) FileID() FileID { return e.Context.File }

func (c *Checker) checkExprFrom(
	expr ast.Expression, parent *Expr, flags ...exprMode,
) *Expr {
	return c.checkExpr(expr, parent.NewChild(flags...))
}

func (c *Checker) checkExpr(expr ast.Expression, t *Expr) *Expr {
	if c.debug() {
		c.logger.push(fmt.Sprintf(
			"%T expression at %s:%s",
			expr, c.Module.ResolveFile(t.FileID()), expr.GetRange(),
		))
		defer c.logger.pop()
	}

	switch expr := expr.(type) {
	case *ast.BinaryExpression:
		c.checkBinaryExpr(expr, t)
	case *ast.RelationalExpression:
		c.checkRelationalExpr(expr, t)
	case *ast.UnaryExpression:
		c.checkUnaryExpr(expr, t)
	case *ast.NilLiteral:
		// TODO: Use [ConstValue]s
		c.checkNilLiteral(expr, t)
	case *ast.StringLiteral:
		c.checkStringLiteral(expr, t)
	case *ast.IntegerLiteral:
		// All numeric literals can be used as Float, so `3.0 + 5` is valid.
		// TODO: use ConstValue
		if t.hint != nil && t.hint.Kind() == FloatType {
			t.Type = FloatType
		} else {
			t.Type = Untyped(IntType)
		}
	case *ast.FloatLiteral:
		t.Type = FloatType
	case *ast.BooleanLiteral:
		t.Type = BoolType
	case *ast.Symbol:
		c.checkSymbolExpr(expr, false, t)
	case *ast.MapLiteral:
		c.checkMapLiteral(expr, t)
	case *ast.TupleLiteral:
		c.checkTupleLiteral(expr, t)
	case *ast.ListLiteral:
		c.checkListLiteral(expr, t)
	case *ast.IndexExpression:
		c.checkIndexExpr(expr, nil, t)
	case *ast.CallExpression:
		c.checkCallExpr(expr, t)
	case *ast.EnumLiteral:
		c.checkEnumLiteral(expr, t)
	case *ast.WhenExpression:
		c.checkWhenExpr(expr, t)
	case *ast.LambdaExpression:
		c.checkLambdaExpr(expr, t)
	case *ast.RangeExpression:
		c.checkRangeExpr(expr, t)
	case *ast.RestExpression:
		// TODO: Check for rest expressions where they are allowed, so we can
		// report an error if they are reached here.
		// They only are allowed in:
		// - Calls
		// - Tuples
		// - Lists
		// - Maps
		// - List slices
		err := klarerrs.Node(klarerrs.ErrMisplacedRest, expr)
		err.Label = "Can't use a rest expression here"
		c.fileError(err, t.Context.File)
		t.Type = InvalidType
	case *ast.PipelineExpression:
		c.checkPipelineExpr(expr, t)
	case *ast.BadExpression:
		t.Type = InvalidType
	case *ast.SliceExpression:
		c.checkSliceExpr(expr, t)
	case *ast.ParenExpression:
		c.checkExpr(expr.Expression, t)
	case *ast.RegexLiteral:
		c.checkRegexLiteral(expr, t)
	case *ast.VersionLiteral:
		// These are only parsed within attributes.
		if !t.mode.has(attributeFunc) {
			panic("found version literal outside of attribute")
		}
		// klar._builtin.attributes defines tag Version.
		// TODO: Make this a ConstValue because attributes params require constants
		t.Type = t.Context.LookupRecursive("Version")
	case *ast.ListCastExpression:
		c.checkListCastExpr(expr, t)
	case *ast.MapCastExpression:
		c.checkMapCastExpr(expr, t)
	case *ast.ObjectPipeline:
		c.checkObjectPipeline(expr, t)
	case *ast.ForExpression:
		c.checkForExpr(expr, t)
	case *ast.StructDotInit:
		c.checkStructDotInitExpr(expr, t)
	case *ast.GoExpression:
		c.checkGoExpr(expr, t)
	case *ast.AwaitExpression:
		c.checkAwaitExpr(expr, t)
	case *ast.AssertExpression:
		c.checkAssertExpr(expr, t)
	case *ast.TryExpression:
		c.checkTryExpr(expr, t)
	// TODO: Report errors for these misplaced when-pattern syntax
	// case *ast.Discard:
	// case *ast.AsExpression:
	// case *ast.SubOptions:
	default:
		panic(fmt.Sprintf("unhandled expression node type: %T", expr))
	}
	if t.Type == nil {
		t.Type = InvalidType
	}
	// Ensure a function that returns Nothing isn't being used as a value
	// TODO: Should we move this to function/pipeline/try/await checking?
	if t.Type.Kind() == NothingType && !t.mode.has(exprStmt|allowNothingValue) {
		err := klarerrs.Node(klarerrs.ErrNothingAsValue, expr)
		err.Label = "This expression returns 'Nothing'"
		c.fileError(err, t.Context.File)
	}
	if nr, ok := t.Type.(*NoReturn); ok && t.stmtCtx != nil && !nr.IsTODO() {
		t.stmtCtx.flags |= unreachableStmt
	}
	// Ensure the expression is allowed to be used in t's context ([Expr.mode])
	if filtered, kind := t.IsFiltered(expr); filtered {
		_ = kind
	}
	// Record the expression node and its *Expr
	c.Info.Expressions[expr] = t
	return t
}

// IsFiltered reports whether the given node is disallowed based on e's mode.
// This is to ensure specific types of nodes don't appear in certain targets,
// such as 'when' expressions in string interpolations. A human-friendly
// name of the node is returned if filtered is false.
func (e *Expr) IsFiltered(expr ast.Expression) (filtered bool, node string) {
	// TODO: Only literals should be allowed in [attributeFunc] mode
	return
}

// If valid, t's Type will be set to an [*Object].
func (c *Checker) checkSymbolExpr(s *ast.Symbol, allowType bool, t *Expr) {
	t.Type = InvalidType
	var (
		name = s.Identifier
		obj  = t.Context.LookupRecursive(name)
		fid  = t.Context.File
	)
	if obj == nil {
		c.fileError(klarerrs.Undefined(name, s.Range), fid)
		return
	}
	// If the target value hasn't been completed yet, typecheck it
	if Underlying(obj.Type) == nil {
		c.checkDeclaration(obj)
	}
	t.Type = obj
	obj.Context.markUsed(obj) // Mark it as used in the context it was declared in
	switch {
	case !obj.IsTypeName():
	case t.hint != nil && t.hint.Kind() == KindFunction:
		// Allowed if t.hint is a function (making the expression an initializer)
		// 	parseInt: func(String) -> Result<Int> := Int
		//
		// Find the overload of the initializer this is referring to
	case allowType:
	case t.mode.has(indexLHS) && obj.Kind() == KindEnum:
		// EnumType.item
		// Note that enum literals also have kind KindEnum
	default:
		// Type used as expression
		err := klarerrs.Range(klarerrs.ErrTypeAsValue, s.Range).
			SetParam("kind", kindOf(obj.Type))
		err.Label = quote(name) + " is a type, not a value"
		err.Name = name
		if obj.Context != BuiltInContext {
			err.AddDetail(quote(name)+" was declared here", obj.FilePath(), obj.Range)
		}
		c.fileError(err, fid)
		t.Type = InvalidType
	}
}

func canRangeOver(k Kind) bool {
	switch k {
	case IntType, StringType, FloatType:
		return true
	default:
		return false
	}
}

func (c *Checker) checkRangeExpr(expr *ast.RangeExpression, t *Expr) {
	from, to := c.checkExprFrom(expr.From, t), c.checkExprFrom(expr.To, t)
	iterType := CommonType(from.Type, to.Type)
	reportTypeMismatch := func(a, b ast.Expression, ta, tb Type) {
		err := typeMismatch(ta, tb, b.GetRange())
		err.AddHighlight("This has type "+quoteAka(ta), a.GetRange())
		c.fileError(err, t.FileID())
		t.Type = &List{InvalidType}
	}
	if iterType == nil {
		reportTypeMismatch(expr.From, expr.To, from.Type, to.Type)
		return
	}
	// Step
	if expr.Step != nil {
		step := c.checkExprFrom(expr.Step, t)
		prevIterType := iterType
		if iterType = CommonType(iterType, step.Type); iterType == nil {
			reportTypeMismatch(expr.To, expr.Step, prevIterType, iterType)
			return
		}
	}

	// Check if we can range over the type
	kind := iterType.Kind()
	if !canRangeOver(kind) && kind != InvalidType {
		err := klarerrs.TypeError(
			klarerrs.ErrInvalidRangeType,
			expr.Range, "", from.Type.String(),
		)
		err.Label = "Can't range over this type"
		c.fileError(err, t.Context.File)
		t.Type = &List{iterType}
		return
	}

	// If we range over a string:
	// - The LHS/RHS must be a string constant of a single character
	// - '..<' isn't allowed, and
	// - There must be no step.
	switch {
	case kind != StringType:
	case expr.Step != nil:
		err := klarerrs.Range(klarerrs.ErrStepWithStringRange, expr.Operator.Range())
		err.Label = "Remove the step"
		c.fileError(err, t.Context.File)
	case expr.Operator.Kind == lexer.DotDotLessThan:
		err := klarerrs.Range(klarerrs.ErrOpenStringRange, expr.Operator.Range())
		err.Label = "Change this to '...'"
		// TODO: Hint on what end character to use instead of '..<'
		c.fileError(err, t.Context.File)
	case false:
		// TODO: Check constants for from and to
	}

	// TODO: Constant analysis for range exprs (e.g. '10...1...2')
	t.Type = &List{iterType}
}

func (c *Checker) checkGoExpr(expr *ast.GoExpression, t *Expr) {
	// The parser already checks that the expression is a call
	// TODO: Manually check the LHS of the call, then check
	// the function with the RHS. The parser allows `go Struct()`. Ensure
	// `Struct` is a function.
	if expr.Body != nil {
		// Treated as a function scope, so it can't return or break loops outside of the block
		block := newStmtContext(NewContext(t.Context, t.FileID()), t.FileID(), allowReturn)
		c.recordBlock(expr.Body, block)
		c.checkBlock(expr.Body.Body, block)
		ret := c.inferReturnType(*block.returns)
		t.Type = &Task{ret}
		return
	}
	arg := c.checkExprFrom(expr.Expression, t)
	t.Type = &Task{arg.Type}
}

func (c *Checker) checkAwaitExpr(expr *ast.AwaitExpression, t *Expr) {
	arg := c.checkExprFrom(expr.Expression, t)
	errNotTask := func(typ Type) {
		str := typ.String()
		// TODO: Be more specific (ex. must be a list of Task)
		err := klarerrs.TypeError(klarerrs.ErrTypeMismatch, expr.Range, "Task", str)
		err.Label = "This has type " + str
		c.fileError(err, t.Context.File)
	}
	switch typ := arg.Type; typ.Kind() {
	case KindTask:
		t.Type = As[*Task](typ).Result
	case KindTuple:
		// If `a: Task<A>` and `b: Task<B>`, `await (a, b)` is `(A, B)`
		tupleArg := As[*Tuple](typ)
		tupleRes := &Tuple{Items: make([]Type, len(tupleArg.Items))}
		for i, elem := range tupleArg.Items {
			// TODO:
			taskItem, ok := Underlying(elem).(*Task)
			if !ok {
				errNotTask(elem) // Not a Task
				tupleRes.Items[i] = InvalidType
				continue
			}
			tupleRes.Items[i] = taskItem.Result
		}
		t.Type = tupleRes
	case KindList:
		// If `taskList: [Task<T>]`, `await taskList` is `[T]`
		elem := Underlying(typ).(*List).Elem
		taskElem, ok := elem.(*Task)
		if !ok {
			errNotTask(elem) // Not a Task
			t.Type = &List{InvalidType}
			break
		}
		t.Type = &List{taskElem.Result}
	default:
		t.Type = InvalidType
		errNotTask(typ)
	}
}

func (c *Checker) checkIndexExpr(expr *ast.IndexExpression, lhs Type, t *Expr) {
	if lhs == nil {
		lhs = c.checkExprFrom(expr.Object, t, indexLHS).Type
	}
	if lhs.Kind() == InvalidType {
		t.Type = InvalidType
		return
	}
	// Types that can be indexed by dot implement [Indexer]
	indexer, ok := Underlying(lhs).(Indexer)
	var err *klarerrs.Error
	if expr.Computed {
		rhs := c.checkExprFrom(expr.Property, t)
		// TODO: handle unions (union of #{Int: Any} and [Any]
		// supports computed indexing)
		if compIndexer, ok := Underlying(lhs).(ComputedIndexer); ok {
			err = compIndexer.IndexComputed(rhs.Type, t)
		} else {
			err = indexError(klarerrs.ErrInvalidComputedIndex, rhs.Type, "")
		}

		if err != nil && err.Code == klarerrs.ErrInvalidComputedIndex {
			err.Name = lhs.String()
			// If the user uses a String computed index, suggest using a dot
			// index instead. (TODO: diff)
			if rhs.Type.Kind() == StringType {
				err.Code = klarerrs.ErrDotIndexRequired
				err.Label = "Type " + quote(lhs.String()) +
					" must be indexed via a dot index"
			} else {
				err.Label = "Can't index type " + quote(lhs.String()) +
					" using type " + quote(rhs.Type.String())
			}
		}
	} else if ok {
		// Dot-index
		field := expr.Property.(*ast.Symbol).Identifier
		err = indexer.Index(field, t)
		if o, ok := t.Type.(*Object); ok && Underlying(o.Type) == nil {
			c.checkDeclaration(o)
		}
	}

	switch {
	case !ok, t.Type == nil && err == nil:
		err := klarerrs.Node(klarerrs.ErrInvalidIndexType, expr.Object)
		err.Info = klarerrs.TypeErrorInfo{GotType: lhs.String()}
		err.Label = "Can't index " + klarerrs.WithA(lhs.Kind().String())
		c.fileError(err, t.Context.File)
		t.Type = InvalidType
	case err != nil:
		// Error while indexing, such as:
		// - Indexing using an unknown field
		// - Index out of range for list constants
		// - Non-constant tuple index
		if err.Code == klarerrs.ErrFieldNotFound {
			err.SetParam("type", lhs.String())
		}
		err.Node = expr.Property
		err.Range = expr.Property.GetRange()
		c.fileError(err, t.Context.File)
		t.Type = InvalidType
	}
}

func (c *Checker) checkUnaryExpr(expr *ast.UnaryExpression, t *Expr) {
	rhs := c.checkExprFrom(expr.Right, t)
	t.Type = rhs.Type
	rhsKind := rhs.Type.Kind()
	switch expr.Operator.Kind {
	case lexer.Minus:
		// RHS must be an Int or Float
		if rhsKind != IntType && rhsKind != FloatType {
			got := rhs.Type.String()
			err := klarerrs.Node(klarerrs.ErrNegateNonNumeric, expr.Right)
			err.Label = "This has type " + quote(got)
			err.Info = klarerrs.TypeErrorInfo{GotType: got}
			c.fileError(err, t.Context.File)
			t.Type = InvalidType
		}
	case lexer.Not:
		// RHS must be Bool
		if rhsKind != BoolType {
			got := rhs.Type.String()
			err := klarerrs.Node(klarerrs.ErrNegateNonNumeric, expr.Right)
			err.Label = "This has type " + quote(got)
			err.Info = klarerrs.TypeErrorInfo{GotType: got}
			err.Name = expr.Operator.String()
			// Provide a hint if the user tried to negate an optional:
			// 	isNil := !optional
			if rhsKind == KindOptional {
				hintWithDiff(
					err, "To check for non-nilness, use 'expr != none'",
					&klarerrs.DeletedRange{Range: expr.Operator.Range()},
					&klarerrs.AddedString{
						Pos:    expr.Right.GetRange().End.Add(0, 1),
						String: "!= none",
					},
				)
			}
			c.fileError(err, t.Context.File)
		}
		t.Type = BoolType
	default:
		panic(fmt.Sprintf("unhandled unary operator: %q", expr.Operator))
	}
}

func (c *Checker) checkBinaryExpr(expr *ast.BinaryExpression, t *Expr) {
	lhs := c.checkExprFrom(expr.Left, t)
	rhs := t.NewChild()
	if op := expr.Operator.Kind; op != lexer.In && op != lexer.NotIn {
		// Hint is inaccurate for in/!in operations
		// TODO: Should we set the hint to `String | #{T: Any} | [T]` so
		// enums can be used (`enum in [.a, .b]`)?
		rhs.hint = lhs.Type
	}
	c.checkExpr(expr.Right, rhs)
	t.Type = c.checkBinaryOperation(
		expr.Operator, lhs.Type, rhs.Type,
		expr.Left, expr.Right, expr, t.FileID(),
	)
}

func (c *Checker) checkBinaryOperation(op ast.Operator, lhs, rhs Type,
	lhsNode, rhsNode ast.Expression, fullExpr *ast.BinaryExpression, fid FileID,
) (result Type) {
	lhsKind, rhsKind := lhs.Kind(), rhs.Kind()
	mismatchedOperandsError := func() *klarerrs.Error {
		err := klarerrs.Node(klarerrs.ErrOperandTypeMismatch, rhsNode)
		err.Name = op.String()
		err.AddHighlight("This has type "+quoteAka(lhs), lhsNode.GetRange())
		err.Label = "This has type " + quoteAka(rhs)
		return err
	}
	// TODO: handle unions
	// TODO: Respect t.hint. If the hint is `Int | Float`, `Int(2) and 5.5` is allowed
	switch op.Kind {
	case lexer.AndAnd, lexer.OrOr:
		result = BoolType
		for _, side := range [...]struct {
			t    Type
			node ast.Expression
		}{{lhs, lhsNode}, {rhs, rhsNode}} {
			if Compatible(side.t, BoolType) {
				continue
			}
			err := typeMismatch(BoolType, side.t, side.node.GetRange())
			err.Code = klarerrs.ErrNonBoolLogical
			err.Name = op.String()
			err.Label = "This has type " + quote(lhs.String())
			c.fileError(err, fid)
			return InvalidType
		}
	case lexer.Plus:
		// Int, Float, String, List, Map
		if result = CommonType(lhs, rhs); result == nil {
			c.fileError(mismatchedOperandsError(), fid)
			return InvalidType
		}
		switch result.Kind() {
		case IntType, StringType, FloatType, KindList, KindMap:
		default:
			err := klarerrs.Node(klarerrs.ErrInvalidAdditionType, rhsNode)
			err.AddHighlight("", lhsNode.GetRange())
			err.Label = "These have type " + quoteAka(result)
			err.Name = result.Kind().String()
			if result.Kind() == KindTuple {
				// Hint on tuple + tuple to use (tuple1..., tuple2...) instead
				// TODO: Can we use a line diff instead? (old line - new line)
				// Do this after we're able to print AST nodes
				hintWithDiff(
					err, "To concatenate tuples, spread them into a single tuple",
					klarerrs.AddedString{Pos: lhsNode.GetRange().Start, String: "("},
					klarerrs.AddedString{Pos: lhsNode.GetRange().End, String: "...,"},
					klarerrs.DeletedRange{
						ranges.Range{op.Range().Start, op.Range().End.Add(0, 1)},
					},
					klarerrs.AddedString{Pos: rhsNode.GetRange().End, String: "...)"},
				)
			}
			c.fileError(err, fid)
		}
	case lexer.Asterisk:
		// Int, Float, String * Int
		if lhsKind == StringType {
			if !Compatible(rhs, IntType) {
				err := typeMismatch(IntType, rhs, rhsNode.GetRange())
				err.Code = klarerrs.ErrInvalidStringMult
				err.Label = "Expected an Int, but this is " + quote(rhs.String())
				err.AddHighlight(
					"This has type "+quote(lhs.String()), // String
					lhsNode.GetRange(),
				)
				c.fileError(err, fid)
				return InvalidType
			}
			return StringType
		} else if lhsKind == IntType && rhsKind == StringType {
			// Wrong order. String * Int, not Int * String
			var err *klarerrs.Error
			if fullExpr != nil {
				err = klarerrs.Node(klarerrs.ErrIntTimesString, fullExpr)
				err.Label = "Switch these operands"
			} else {
				err = klarerrs.Node(klarerrs.ErrIntTimesString, rhsNode)
				err.Label = "The operand on the right should be the Int"
			}
			c.fileError(err, fid)
			return StringType
		}
		fallthrough
	case lexer.Minus, lexer.Slash, lexer.Percent, lexer.Caret,
		lexer.LessThan, lexer.LessEqualTo, lexer.GreaterThan, lexer.GreaterEqualTo:
		// Int, Float
		if result = CommonType(lhs, rhs); result == nil {
			// Mismatched operands
			c.fileError(mismatchedOperandsError(), fid)
			return InvalidType
		}
		if kind := result.Kind(); kind != IntType && kind != FloatType {
			var err *klarerrs.Error
			if fullExpr != nil {
				err = klarerrs.Node(klarerrs.ErrInvalidArithType, fullExpr)
			} else {
				err = klarerrs.Node(klarerrs.ErrInvalidArithType, rhsNode)
				err.AddHighlight("", lhsNode.GetRange())
			}
			err.Name = op.String()
			err.Label = "These have type " + quote(result.String())
			c.fileError(err, fid)
			return InvalidType
		}
		switch op.Kind {
		case lexer.LessThan, lexer.LessEqualTo, lexer.GreaterThan, lexer.GreaterEqualTo:
			result = BoolType
		}
	case lexer.EqualEqual, lexer.NotEqual:
		compType := CommonType(lhs, rhs)
		if compType == nil {
			c.fileError(mismatchedOperandsError(), fid)
			return BoolType
		}
		// In Klar, all types can be compared for equality
		if compType.Kind() == KindFunction {
			// If comparing functions, we can report an error if different function
			// references are compared, because the result is always known.
			// 	func a() = 1
			// 	func b() = 1
			// 	_ = a == b
			// If at least 1 is a variable, we won't report an error.
			// 	fn := a
			//  _ = fn == b // Valid without constant analysis
		}
		return BoolType
	case lexer.And, lexer.Or:
		// Distributive: any type, but both sides must be the same
		if result = CommonType(lhs, rhs); result == nil {
			// Both operands must have the same type
			c.fileError(mismatchedOperandsError(), fid)
			return InvalidType
		}
		// TODO: Ensure they are used in another binary operation. With that
		// requirement, the type of this expression is trivial.
		// 	Allowed: a and b > 5
		// 	Not allowed: _ = a and b
	case lexer.In, lexer.NotIn:
		// T in [T], K in #{K: V}, "s" in "str"
		result = BoolType
		switch rhsKind {
		case KindMap:
			mp, isTyped := Underlying(rhs).(*Map)
			if !isTyped {
				// If the RHS is untyped, its value is #{}. `_ in #{}` is always false
				// TODO: error. When saying "always false", be aware to say "always true"
				// if !in is used.
				return
			}
			if !Compatible(lhs, mp.Key) {
				err := typeMismatch(mp.Key, lhs, lhsNode.GetRange())
				err.AddHighlight(
					"This map has type "+quote(mp.String()),
					rhsNode.GetRange(),
				)
				// If the LHS is a map value instead of a key, show a hint (V in #{K: V})
				if Compatible(lhs, mp.Value) {
					var not string
					if op.Kind == lexer.NotIn {
						not = "n't"
					}
					err.Hintf(
						"The %s operator checks if a key, not a value, is%s in a map",
						op, not,
					)
				}
				c.fileError(err, fid)
			}
		case KindList:
			list, isTyped := Underlying(rhs).(*List)
			if !isTyped {
				// TODO: error
				return
			}
			if !Compatible(lhs, list.Elem) {
				err := typeMismatch(list.Elem, lhs, lhsNode.GetRange())
				err.AddHighlight(
					"This list has type "+quote(list.String()),
					rhsNode.GetRange(),
				)
				c.fileError(err, fid)
			}
		case StringType:
			if !Compatible(lhs, StringType) {
				c.fileError(typeMismatch(StringType, lhs, lhsNode.GetRange()), fid)
			}
		default:
			err := klarerrs.Node(klarerrs.ErrInvalidInOperand, rhsNode)
			err.Label = "This has type " + quote(rhs.String())
		}
	default:
		panic(fmt.Sprintf("unhandled binary operator: %q", op))
	}
	return result
}

func (c *Checker) checkRelationalExpr(expr *ast.RelationalExpression, t *Expr) {
	for i, op := range expr.Operators {
		lhsNode, rhsNode := expr.Expressions[i], expr.Expressions[i+1]
		lhs := c.checkExprFrom(lhsNode, t)
		rhs := c.checkExpr(rhsNode, t.NewChild().withHint(lhs.Type))
		c.checkBinaryOperation(op, lhs.Type, rhs.Type, lhsNode, rhsNode, nil, t.FileID())
	}
	t.Type = BoolType
}

func (c *Checker) checkSliceExpr(expr *ast.SliceExpression, t *Expr) {
	lhs := c.checkExprFrom(expr.Object, t)
	for _, part := range [...]ast.Expression{expr.From, expr.To} {
		if part == nil {
			continue
		}
		e := c.checkExprFrom(part, t)
		if e.Kind() != IntType {
			err := klarerrs.Node(klarerrs.ErrNonNumericIndex, part).SetParam("op", "slice")
			err.Label = "Can't slice a list using type " + quoteAka(e.Type)
			err.Info = klarerrs.TypeErrorInfo{lhs.Type.Kind().String(), e.Type.String()}
			c.fileError(err, t.FileID())
		}
	}
	switch lhs.Type.Kind() {
	case KindList, StringType:
		// TODO: If index is `...0`, don't make the type optional
		t.Type = &Optional{lhs.Type}
	case KindTuple:
		// TODO: Check constants and slice
		t.Type = lhs.Type
	default:
		t.Type = lhs.Type
	}
}

func (c *Checker) checkStructDotInitExpr(expr *ast.StructDotInit, t *Expr) {
	hint := t.hint
	if hint != nil && hint.Kind() == KindResult {
		// If the target type is a result, allow the shorthand, which will
		// refer to the success type, even if it isn't a struct. Initializing
		// an error will always have to be explicit.
		hint = As[*Result](hint).Success
	}
	t.Type = hint
	switch {
	case hint == nil:
		t.Type = &UntypedInit{kind: KindStruct, Node: expr, Params: expr.Params}
		// Check the parameters once its type is inferred
		c.queue(func() { c.checkCallArgs(t.Type, expr.Params, t) }, false)
		return
	case hint.Kind() == KindStruct || hint.Kind() == ErrorType:
		// Valid
	default:
		err := klarerrs.Node(klarerrs.ErrInvalidStructShorthand, expr)
		err.Label = "Type " + quoteAka(hint) + " isn't a struct"
		// Unions, optionals, and results can't be written as function callees
		if isTypeName(hint) || IsConcreteType(hint) {
			hintWithDiff(
				err, "Replace '.' with "+quote(hint.String()),
				klarerrs.DeletedRange{ranges.SingleChar(expr.Range.Start)},
				klarerrs.AddedString{Pos: expr.Range.Start, String: hint.String()},
			)
		}
		c.fileError(err, t.FileID())
	}
	c.checkCallArgs(t.Type, expr.Params, t)
}

func (c *Checker) checkAssertExpr(expr *ast.AssertExpression, t *Expr) {
	lhs := c.checkExprFrom(expr.Expression, t)
	switch lhs.Kind() {
	case KindOptional:
		t.Type = As[*Optional](lhs.Type).Elem
	case KindResult:
		t.Type = As[*Result](lhs.Type).Success
	default:
		err := klarerrs.Node(klarerrs.ErrInvalidAssertType, expr.Expression)
		err.Label = "This has type " + quote(lhs.Type.String())
		c.fileError(err, t.Context.File)
		t.Type = lhs.Type
		return
	}
}

func (c *Checker) checkTryExpr(expr *ast.TryExpression, t *Expr) {
	rhs := c.checkExprFrom(expr.Expression, t)
	if rhs.Kind() == InvalidType {
		t.Type = InvalidType
		return
	}
	if rhs.Kind() != KindResult {
		err := klarerrs.Node(klarerrs.ErrNonResultInTry, expr.Expression)
		err.Label = "This has type " + quote(rhs.Type.String())
		c.fileError(err, t.Context.File)
		t.Type = rhs.Type
		return
	}
	res := Underlying(rhs.Type).(*Result)
	t.Type = res.Success
}

func (c *Checker) checkListCastExpr(expr *ast.ListCastExpression, t *Expr) {
	elem := c.parseType(expr.Type, t.Context)
	c.checkCallArgs(&List{elem}, expr.Args, t)
}

func (c *Checker) checkMapCastExpr(expr *ast.MapCastExpression, t *Expr) {
	key := c.parseType(expr.KeyType, t.Context)
	val := c.parseType(expr.ValueType, t.Context)
	c.checkCallArgs(&Map{key, val}, expr.Args, t)
}

func (c *Checker) checkLambdaExpr(expr *ast.LambdaExpression, t *Expr) {
	// Both are lazy-initialized
	var untyped *UntypedLambda
	var typed *Lambda

	// No parameters means the lambda is typed
	if len(expr.Params) == 0 {
		typed = &Lambda{}
	}
	// For now, we're only collecting the explicit types for params and returns
	for i, pair := range expr.Params {
		// Default value
		var def Type
		if pair.Value != nil {
			def = c.checkExprFrom(pair.Value, t).Type
		}

		// No explicit type: untyped
		if pair.Type == nil {
			if untyped == nil {
				untyped = &UntypedLambda{
					Vars: make([]UntypedLambdaParam, 0, len(expr.Params)),
				}
			}
			for _, vr := range pair.Keys {
				var name string
				if sym, ok := vr.(*ast.Symbol); ok {
					name = sym.Identifier
				} else {
					// TODO: Stringify ast.Assignable
					name = "<destructure>"
				}
				untyped.Vars = append(untyped.Vars, UntypedLambdaParam{
					Name:    name,
					Default: def,
				})
			}
			continue
		}

		// Typed lambda
		if typed == nil {
			typed = &Lambda{Params: make([]Type, 0, len(expr.Params))}
		}
		typ, variadic := c.parseTypeOrVariadic(pair.Type, t.Context)
		if variadic {
			typed.Variadic = true
			// Ensure this is the last param
			if i < len(expr.Params)-1 || len(pair.Keys) > 1 {
			}
		}
		for range pair.Keys {
			typed.Params = append(typed.Params, typ)
		}
		// Ensure the default value is compatible with the explicit type
		if def != nil && !Compatible(def, typ) {
			c.fileError(typeMismatch(typ, def, pair.Value.GetRange()), t.FileID())
		}
	}

	if untyped != nil {
		t.Type = untyped
		// At the time this is run, the function's params and return type
		// should be resolved into t.Type.
		c.queue(func() { c.checkLambdaBody(expr, t) }, true)
	} else {
		t.Type = typed
		// If the lambda is typed, we can check the function body right away.
		// Right now, we may or may not have an explicit return type.
		c.checkLambdaBody(expr, t)
	}
}

// TODO: Factor functionality from [Checker.checkFuncBody]
func (c *Checker) checkLambdaBody(expr *ast.LambdaExpression, t *Expr) {
	l, ok := Underlying(t.Type).(*Lambda)
	if !ok {
		return // Lambda is still untyped
	}
	bodyCtx := NewContext(t.Context, t.Context.File)
	// Declare variables
	var i int
	for _, pair := range expr.Params {
		for _, assg := range pair.Keys {
			var typ Type
			if i >= len(l.Params) {
				// Type mismatch already reported
				typ = InvalidType
			} else {
				typ = l.Params[i]
			}
			i++
			// TODO: followDestructure skips non-name variables because errors are
			// pre-reported for variable declarations, but not lambdas. Find a way
			// to report those errors (another option to followDestructure is
			// preferred over another pass).
			for dest, typ := range c.followDestructure(
				assg, typ, t.FileID(),
				cmp.Or[ast.Node](pair.Type, pair.Value, assg).GetRange(), true,
			) {
				sym := dest.(*ast.Symbol)
				vr := NewObject(sym.Identifier, t.FileID(), sym.Range, c.Module, nil)
				NewVariable(vr, FuncParamVar, typ)
				c.declare(bodyCtx, vr)
			}
		}
	}

	// Body
	if expr.Block != nil {
		// Creating a new stmtCtx without a parent so the body can't return or
		// break the parent's loops
		sctx := newStmtContext(bodyCtx, t.Context.File, allowReturn)
		c.recordBlock(expr.Block, sctx)
		c.checkBlock(expr.Block.Body, sctx)
	} else {
		c.checkExpr(expr.Expr, t.NewChild(allowNothingValue).withContext(bodyCtx))
	}

	// TODO: Check returns
}

const PipelineResultName = "value"

func (c *Checker) checkPipelineExpr(expr *ast.PipelineExpression, t *Expr) {
	first := c.checkExprFrom(expr.Steps[0].(ast.Expression), t)
	var (
		valObj = NewObject(
			PipelineResultName, t.Context.File, expr.Range, c.Module, nil,
		)
		valVar      = NewVariable(valObj, PipelineVar, first.Type)
		pipelineCtx = NewContext(t.Context, t.Context.File)
	)
	pipelineCtx.Declare(valObj)
	for _, step := range expr.Steps[1:] {
		if ret, ok := step.(*ast.ReturnStatement); ok {
			if !t.mode.has(exprStmt) {
				// A `return` in a pipeline is only allowed in expresion statements.
				// Not allowed:
				// 	_ = a() |> b |> return
				err := klarerrs.Node(klarerrs.ErrReturnInPipelineExpr, ret)
				err.Label = "This is only allowed when the pipeline is a statement"
				c.fileError(err, t.Context.File)
			}
			c.checkReturnStmt(ret, t.stmtCtx)
			continue // Should be the last step
		}
		// TODO: Ensure each step is a call, and pass `value` as a param
		// See RFC #8: https://github.com/ProCode-Software/klar/discussions/11
		e := c.checkExpr(step.(ast.Expression), t.NewChild().withContext(pipelineCtx))
		valVar.Type = e.Type // Set `value` to the type of the last step
	}
	t.Type = valVar.Type
}

func (c *Checker) checkObjectPipeline(expr *ast.ObjectPipeline, t *Expr) {
	obj := c.checkExprFrom(expr.Object, t)
	for _, step := range expr.Steps {
		lhs := t.NewChild()
		switch step := step.(type) {
		case *ast.CallExpression:
			c.checkIndexExpr(&ast.IndexExpression{
				Object:   expr.Object,
				Property: step.Callee,
			}, obj.Type, lhs)
			c.checkCallArgs(lhs.Type, step.Args, t.NewChild())
		case *ast.AssignmentStatement:
			c.checkIndexExpr(&ast.IndexExpression{
				Object:   expr.Object,
				Property: step.Assignee[0],
			}, obj.Type, lhs)
			rhs := c.checkExpr(step.Values[0], t.NewChild().withHint(lhs.Type))
			c.checkAssignment(
				lhs.Type, rhs.Type, step.Assignee[0], step.Values[0],
				step.Operator.Uncompound(), t.FileID(),
			)
		default:
			panic(fmt.Sprintf("invalid step in object pipeline: %T", step))
		}
	}
}

func (c *Checker) checkForExpr(expr *ast.ForExpression, t *Expr) {
	bodyCtx, kind := c.checkForVars(expr.Variables, expr.Iterator, t.Context, t.NewChild)
	res := c.checkExpr(expr.Value, t.NewChild().withContext(bodyCtx))
	switch kind {
	case InvalidType:
		t.Type = InvalidType
	case KindList, IntType, StringType:
		// Any type is valid. It will be put into a list
		//
		// TODO: Should we reconsider allowing loops over String and Int?
		// Or, should a loop over a String return a String?
		t.Type = &List{res.Type}
	case KindMap:
		// For expression over map must yield a pair (K, V)
		tup, ok := Underlying(res.Type).(*Tuple)
		if !ok || tup.Len() != 2 {
			err := klarerrs.Node(klarerrs.ErrForExprResMismatch, expr.Value).
				SetParam("required", "a pair (K, V)").SetParam("iterKind", "a map")
			c.fileError(err, t.FileID())
			t.Type = &Map{InvalidType, InvalidType}
			return
		}
		t.Type = &Map{tup.Items[0], tup.Items[1]}
	default:
		panic("unhandled kind returned from checkForVars: " + kind.String())
	}
}

// canSpreadTupleIntoList checks if the provided tuple can be spread into a list.
// That is true if the types of all of the tuple's items are common.
// If they are in common, the common type is returned. Otherwise,
// canSpreadTupleIntoList returns nil and an error if the tuple can't be spread.
func canSpreadTupleIntoList(t *Tuple) (commonType Type, err *klarerrs.Error) {
	for _, item := range t.Items {
		if commonType = CommonType(commonType, item); commonType == nil {
			return nil, &klarerrs.Error{
				Code:  klarerrs.ErrRestUncommonTuple,
				Label: "This tuple has type " + t.String(),
			}
		}
	}
	return commonType, nil
}