Skip to content

Database governance built for humans and agents — controlling changes and access across every major database.

41.4 KB
Raw Blame
package pg

import (
	"strings"

	"github.com/pkg/errors"

	"github.com/bytebase/omni/pg/ast"
	"github.com/bytebase/omni/pg/catalog"
	plpgsqlast "github.com/bytebase/omni/pg/plpgsql/ast"
	plpgsqlparser "github.com/bytebase/omni/pg/plpgsql/parser"

	"github.com/bytebase/bytebase/backend/plugin/parser/base"
)

// snapshotFunc is a function's language and body as the schema snapshot
// defines it.
type snapshotFunc struct {
	language string
	body     string
}

type funcBodyAnalysis struct {
	sourceColumns    []base.SourceColumnSet
	predicateColumns base.SourceColumnSet
}

// analyzeFunctionBody analyzes a user-defined function body and returns per-column
// source column sets. Results are cached by function OID on the extractor.
// A nil value in the cache means analysis is in progress (recursion sentinel).
// On parse errors, it degrades gracefully by returning empty sets.
func (e *omniQuerySpanExtractor) analyzeFunctionBody(proc *catalog.UserProc) []base.SourceColumnSet {
	analysis := e.analyzeFunctionBodyForProc(proc)
	e.mergeFunctionSourceTables(analysis.sourceColumns)
	mergeSourceColumnSetInto(e.predicateColumns, analysis.predicateColumns)
	return analysis.sourceColumns
}

func (e *omniQuerySpanExtractor) analyzeFunctionBodyForProc(proc *catalog.UserProc) *funcBodyAnalysis {
	// Check cache.
	if cached, ok := e.funcBodyCache[proc.OID]; ok {
		if cached == nil {
			// In-progress sentinel — recursive call. Return empty sets.
			return &funcBodyAnalysis{
				sourceColumns:    makeEmptySets(proc),
				predicateColumns: make(base.SourceColumnSet),
			}
		}
		return cached
	}

	// Store nil sentinel to detect recursion.
	e.funcBodyCache[proc.OID] = nil
	outerPredicateColumns := e.predicateColumns
	bodyPredicateColumns := make(base.SourceColumnSet)
	e.predicateColumns = bodyPredicateColumns
	defer func() {
		e.predicateColumns = outerPredicateColumns
	}()

	// The catalog keeps each overload's own body. A function it could not
	// install is a stand-in with a placeholder body, and the snapshot cannot
	// tell which overload it stands for, so every overload's body is analyzed
	// and merged.
	defs := []snapshotFunc{{language: proc.Language, body: proc.Body}}
	if proc.Schema != nil {
		key := strings.ToLower(proc.Schema.Name + "." + proc.Name)
		if e.standInFuncs[key] && len(e.snapshotFuncs[key]) > 0 {
			defs = e.snapshotFuncs[key]
		}
	}

	var result []base.SourceColumnSet
	var err error
	for _, def := range defs {
		defResult, defErr := e.analyzeBodyAs(proc, def)
		if defErr != nil {
			err = defErr
			continue
		}
		if len(defs) == 1 {
			result = defResult
			break
		}
		for i, set := range defResult {
			if i >= len(result) {
				result = append(result, make(base.SourceColumnSet))
			}
			mergeSourceColumnSetInto(result[i], set)
		}
	}

	if err != nil && result == nil {
		// On error, cache empty sets so we don't retry. The conditions found
		// before the error still run, so they stay.
		e.funcBodyCache[proc.OID] = &funcBodyAnalysis{
			sourceColumns:    makeEmptySets(proc),
			predicateColumns: cloneSourceColumnSet(bodyPredicateColumns),
		}
		return e.funcBodyCache[proc.OID]
	}

	e.funcBodyCache[proc.OID] = &funcBodyAnalysis{
		sourceColumns:    result,
		predicateColumns: cloneSourceColumnSet(bodyPredicateColumns),
	}
	return e.funcBodyCache[proc.OID]
}

func (e *omniQuerySpanExtractor) analyzeBodyAs(proc *catalog.UserProc, def snapshotFunc) ([]base.SourceColumnSet, error) {
	switch strings.ToLower(def.language) {
	case "plpgsql":
		return e.analyzePLpgSQLBody(proc, def.body)
	case "sql":
		return e.analyzeSQLBody(def.body)
	default:
		// Unsupported language (C, internal, etc.) — unknown lineage.
		return makeEmptySets(proc), nil
	}
}

func cloneSourceColumnSet(src base.SourceColumnSet) base.SourceColumnSet {
	dst := make(base.SourceColumnSet)
	for k, v := range src {
		dst[k] = v
	}
	return dst
}

func mergeSourceColumnSetInto(dst, src base.SourceColumnSet) {
	for k, v := range src {
		dst[k] = v
	}
}

func (e *omniQuerySpanExtractor) mergeFunctionSourceTables(bodySets []base.SourceColumnSet) {
	for _, colSet := range bodySets {
		for k := range colSet {
			e.funcSourceColumns[base.ColumnResource{
				Server:   k.Server,
				Database: k.Database,
				Schema:   k.Schema,
				Table:    k.Table,
			}] = true
		}
	}
}

func makeEmptySets(proc *catalog.UserProc) []base.SourceColumnSet {
	n := countOutputParams(proc)
	if n == 0 {
		n = 1 // scalar return
	}
	sets := make([]base.SourceColumnSet, n)
	for i := range sets {
		sets[i] = make(base.SourceColumnSet)
	}
	return sets
}

func countOutputParams(proc *catalog.UserProc) int {
	count := 0
	for _, mode := range proc.ArgModes {
		if mode == 'o' || mode == 't' || mode == 'b' {
			count++
		}
	}
	return count
}

func (e *omniQuerySpanExtractor) analyzeSQLBody(body string) ([]base.SourceColumnSet, error) {
	if body == "" {
		return nil, nil
	}

	stmts, err := ParsePg(body)
	if err != nil {
		return nil, errors.Wrapf(err, "failed to parse SQL function body")
	}

	// Every statement in the body runs, so each one's conditions count; the
	// last one returns the function's result.
	last := -1
	for i, stmt := range stmts {
		if stmt.AST != nil {
			last = i
		}
	}
	var result []base.SourceColumnSet
	for i, stmt := range stmts {
		if stmt.AST == nil {
			continue
		}
		accesses := e.accessTablesOf(stmt.Text)
		// The caller reads what the body reads, whether or not the result shows it.
		mergeSourceColumnSetInto(e.funcSourceColumns, accesses)
		selStmt, ok := stmt.AST.(*ast.SelectStmt)
		if !ok {
			// The analyzer reads SELECT alone, so another statement's conditions
			// and RETURNING list are matched by name.
			e.collectFallbackPredicateColumns(stmt.AST, accesses)
			returning := e.returningLineage(stmt.AST, accesses)
			if i == last {
				result = returning
			} else {
				for _, set := range returning {
					mergeSourceColumnSetInto(e.predicateColumns, set)
				}
			}
			continue
		}
		query, err := e.analyzeSelect(selStmt)
		if err != nil {
			e.collectFallbackPredicateColumns(selStmt, accesses)
			if i != last {
				e.collectDiscardedOutputColumns(nil, selStmt, accesses)
				continue
			}
			// Fall back to parse-tree extraction when analysis fails
			// (e.g., nested function calls, parameter references).
			fallbackResults := e.extractFallbackColumns(selStmt)
			if len(fallbackResults) == 0 {
				return nil, errors.Wrapf(err, "failed to analyze SQL function body")
			}
			result = make([]base.SourceColumnSet, len(fallbackResults))
			for j, fr := range fallbackResults {
				result[j] = fr.SourceColumns
			}
			continue
		}
		e.collectStatementPredicateColumns(query, selStmt, accesses)
		if i == last {
			result = e.extractFuncLineage(query)
		} else {
			e.collectDiscardedOutputColumns(query, selStmt, accesses)
		}
	}
	return result, nil
}

func (e *omniQuerySpanExtractor) extractFuncLineage(q *catalog.Query) []base.SourceColumnSet {
	var result []base.SourceColumnSet
	for _, te := range q.TargetList {
		if te.ResJunk {
			continue
		}
		colSet := make(base.SourceColumnSet)
		e.walkExpr(q, te.Expr, colSet)
		result = append(result, colSet)
	}
	return result
}

// variableScope tracks PL/pgSQL variable source columns with nested scoping.
type variableScope struct {
	vars   map[string]base.SourceColumnSet
	parent *variableScope
}

func newVariableScope(parent *variableScope) *variableScope {
	return &variableScope{
		vars:   make(map[string]base.SourceColumnSet),
		parent: parent,
	}
}

func (s *variableScope) set(name string, sources base.SourceColumnSet) {
	s.vars[strings.ToLower(name)] = sources
}

func (s *variableScope) get(name string) (base.SourceColumnSet, bool) {
	lower := strings.ToLower(name)
	for scope := s; scope != nil; scope = scope.parent {
		if v, ok := scope.vars[lower]; ok {
			return v, true
		}
	}
	return nil, false
}

func (s *variableScope) merge(name string, sources base.SourceColumnSet) {
	lower := strings.ToLower(name)
	existing, ok := s.get(lower)
	if !ok {
		existing = make(base.SourceColumnSet)
	}
	merged := make(base.SourceColumnSet)
	for k, v := range existing {
		merged[k] = v
	}
	for k, v := range sources {
		merged[k] = v
	}
	s.vars[lower] = merged
}

// plpgsqlAnalyzer holds state for analyzing a single PL/pgSQL function body.
type plpgsqlAnalyzer struct {
	extractor *omniQuerySpanExtractor
	scope     *variableScope
	// returnResults collects per-column source sets from all RETURN QUERY paths.
	returnResults [][]base.SourceColumnSet
	// cteMap holds CTE definitions for resolving column refs through CTEs.
	cteMap       map[string]*ast.SelectStmt
	resolvingCTE map[cteResolveKey]bool
	// qualifiedFrom marks fromTables keys whose FROM item carried an
	// explicit schema qualifier, so fallback resolution does not probe the
	// search path for them. Reset per fallback statement; nested subquery
	// collection during one statement accumulates into the same scope.
	qualifiedFrom map[string]bool
}

type cteResolveKey struct {
	sel *ast.SelectStmt
	col string
}

func (e *omniQuerySpanExtractor) analyzePLpgSQLBody(proc *catalog.UserProc, body string) ([]base.SourceColumnSet, error) {
	if body == "" {
		return makeEmptySets(proc), nil
	}

	block, err := plpgsqlparser.Parse(body)
	if err != nil {
		return nil, errors.Wrapf(err, "failed to parse PL/pgSQL function body")
	}

	analyzer := &plpgsqlAnalyzer{
		extractor: e,
		scope:     newVariableScope(nil),
	}

	// Add function input parameters to scope so they can be substituted in
	// embedded SQL. Output/table params ('o', 't') are NOT added because their
	// names often collide with column names in the function body's queries
	// (e.g., RETURNS TABLE(a int, b int) where a, b are also column names).
	for i, name := range proc.ArgNames {
		if name == "" {
			continue
		}
		if i < len(proc.ArgModes) {
			mode := proc.ArgModes[i]
			if mode == 'o' || mode == 't' {
				continue
			}
		}
		analyzer.scope.set(name, make(base.SourceColumnSet))
	}

	analyzer.walkBlock(block)

	nCols := countOutputParams(proc)
	if nCols == 0 {
		nCols = 1
	}

	return analyzer.mergeReturnResults(nCols), nil
}

func (a *plpgsqlAnalyzer) walkBlock(block *plpgsqlast.PLBlock) {
	// Push scope for declarations.
	a.scope = newVariableScope(a.scope)
	defer func() { a.scope = a.scope.parent }()

	// Process declarations.
	for _, decl := range block.Declarations {
		switch d := decl.(type) {
		case *plpgsqlast.PLDeclare:
			sources := make(base.SourceColumnSet)
			if d.Default != "" {
				sources = a.analyzeEmbeddedExpr(d.Default)
			}
			a.scope.set(d.Name, sources)
		case *plpgsqlast.PLCursorDecl:
			// A cursor carries the columns of its query to what FETCH reads.
			a.scope.set(d.Name, a.analyzeQuerySources(d.Query))
		case *plpgsqlast.PLAliasDecl:
			// Alias references another variable — copy its sources.
			if sources, ok := a.scope.get(d.RefName); ok {
				a.scope.set(d.Name, sources)
			} else {
				a.scope.set(d.Name, make(base.SourceColumnSet))
			}
		default:
		}
	}

	// Process body statements.
	for _, stmt := range block.Body {
		a.walkStmt(stmt)
	}

	// Process exception handlers.
	for _, ex := range block.Exceptions {
		if ew, ok := ex.(*plpgsqlast.PLExceptionWhen); ok {
			for _, stmt := range ew.Body {
				a.walkStmt(stmt)
			}
		}
	}
}

func (a *plpgsqlAnalyzer) walkStmt(node plpgsqlast.Node) {
	switch stmt := node.(type) {
	case *plpgsqlast.PLAssign:
		a.handleAssign(stmt)
	case *plpgsqlast.PLReturnQuery:
		a.handleReturnQuery(stmt)
	case *plpgsqlast.PLReturn:
		a.handleReturn(stmt)
	case *plpgsqlast.PLReturnNext:
		a.handleReturnNext(stmt)
	case *plpgsqlast.PLExecSQL:
		a.handleExecSQL(stmt)
	case *plpgsqlast.PLIf:
		a.handleIf(stmt)
	case *plpgsqlast.PLCase:
		a.handleCase(stmt)
	case *plpgsqlast.PLLoop:
		for _, s := range stmt.Body {
			a.walkStmt(s)
		}
	case *plpgsqlast.PLWhile:
		a.handleCondition(stmt.Condition)
		for _, s := range stmt.Body {
			a.walkStmt(s)
		}
	case *plpgsqlast.PLForI:
		a.handleCondition(stmt.Lower)
		a.handleCondition(stmt.Upper)
		a.handleCondition(stmt.Step)
		for _, s := range stmt.Body {
			a.walkStmt(s)
		}
	case *plpgsqlast.PLForS:
		a.handleForS(stmt)
	case *plpgsqlast.PLForC:
		if sources, ok := a.scope.get(stmt.CursorVar); ok {
			a.scope.merge(stmt.Var, sources)
		}
		for _, s := range stmt.Body {
			a.walkStmt(s)
		}
	case *plpgsqlast.PLForDynS:
		for _, s := range stmt.Body {
			a.walkStmt(s)
		}
	case *plpgsqlast.PLForEachA:
		a.handleCondition(stmt.ArrayExpr)
		for _, s := range stmt.Body {
			a.walkStmt(s)
		}
	case *plpgsqlast.PLBlock:
		a.walkBlock(stmt)
	// PERFORM discards its rows but still runs, so how long it takes reveals
	// what it reads.
	case *plpgsqlast.PLPerform:
		a.handleCondition(stmt.Expr)
	case *plpgsqlast.PLDynExecute:
		a.handleDynExecute(stmt)
	case *plpgsqlast.PLOpen:
		if stmt.Query != "" {
			a.scope.merge(stmt.CursorVar, a.analyzeQuerySources(stmt.Query))
		}
	case *plpgsqlast.PLFetch:
		if sources, ok := a.scope.get(stmt.CursorVar); ok {
			for _, varName := range stmt.Into {
				a.scope.merge(varName, sources)
			}
		}
	case *plpgsqlast.PLCall:
		a.handleCall(stmt)
	// RAISE puts the values of its parameters in the message the caller sees.
	case *plpgsqlast.PLRaise:
		for _, param := range stmt.Params {
			a.handleCondition(param)
		}
	case *plpgsqlast.PLExit:
		a.handleCondition(stmt.Condition)
	case *plpgsqlast.PLAssert:
		a.handleCondition(stmt.Condition)
	// Skip nodes that don't affect lineage:
	// PLNull, PLCommit, PLRollback, PLClose, PLGetDiag
	default:
	}
}

// handleCondition records the columns an expression that steers the body
// reads, directly or through variables: it decides which statements run, and
// so what the function returns and how long it takes.
func (a *plpgsqlAnalyzer) handleCondition(expr string) {
	if strings.TrimSpace(expr) == "" {
		return
	}
	mergeSourceColumnSetInto(a.extractor.predicateColumns, a.analyzeEmbeddedExpr(expr))
	stmts, err := ParsePg("SELECT " + expr)
	if err != nil || len(stmts) != 1 {
		return
	}
	a.addScopeReferences(stmts[0].AST)
}

// addScopeReferences records, as predicates, the columns that the variables
// node reads carry.
func (a *plpgsqlAnalyzer) addScopeReferences(node ast.Node) {
	mergeSourceColumnSetInto(a.extractor.predicateColumns, a.scopeSources(node))
}

// scopeSources returns the columns that the variables node reads carry. A
// variable, or the record variable a qualified reference such as r.ssn names,
// carries the columns it was assigned from.
func (a *plpgsqlAnalyzer) scopeSources(node ast.Node) base.SourceColumnSet {
	sources := make(base.SourceColumnSet)
	ast.Inspect(node, func(n ast.Node) bool {
		if ref, ok := n.(*ast.ColumnRef); ok && ref.Fields != nil && len(ref.Fields.Items) > 0 {
			if name, ok := ref.Fields.Items[0].(*ast.String); ok {
				if varSources, ok := a.scope.get(name.Str); ok {
					mergeSourceColumnSetInto(sources, varSources)
				}
			}
		}
		return true
	})
	return sources
}

// analyzeQuerySources returns every column the output of sql reads, merged.
func (a *plpgsqlAnalyzer) analyzeQuerySources(sql string) base.SourceColumnSet {
	merged := make(base.SourceColumnSet)
	if strings.TrimSpace(sql) == "" {
		return merged
	}
	for _, set := range a.analyzeEmbeddedSQL(sql) {
		mergeSourceColumnSetInto(merged, set)
	}
	return merged
}

// handleCall analyzes the body of the procedure CALL invokes, whatever
// overload it is. The procedure runs for its effects, so the values passed to
// it count as predicates.
func (a *plpgsqlAnalyzer) handleCall(stmt *plpgsqlast.PLCall) {
	stmts, err := ParsePg(stmt.SQLText)
	if err != nil || len(stmts) != 1 {
		return
	}
	call, ok := stmts[0].AST.(*ast.CallStmt)
	if !ok || call.Funccall == nil {
		return
	}
	for _, proc := range a.extractor.userProcsNamed(astStrings(call.Funccall.Funcname)) {
		a.extractor.analyzeFunctionBody(proc)
	}
	if call.Funccall.Args == nil {
		return
	}
	for _, arg := range call.Funccall.Args.Items {
		loc := ast.NodeLoc(arg)
		if loc.Start >= 0 && loc.End > loc.Start && loc.End <= len(stmt.SQLText) {
			a.handleCondition(stmt.SQLText[loc.Start:loc.End])
			continue
		}
		a.addScopeReferences(arg)
	}
}

func (a *plpgsqlAnalyzer) handleAssign(stmt *plpgsqlast.PLAssign) {
	varName := extractBaseVarName(stmt.Target)
	sources := a.analyzeEmbeddedExpr(stmt.Expr)
	a.scope.merge(varName, sources)
}

func (a *plpgsqlAnalyzer) handleReturnQuery(stmt *plpgsqlast.PLReturnQuery) {
	if stmt.Query == "" {
		return
	}
	results := a.analyzeEmbeddedSQL(stmt.Query)
	if len(results) > 0 {
		a.returnResults = append(a.returnResults, results)
	}
}

func (a *plpgsqlAnalyzer) handleReturn(stmt *plpgsqlast.PLReturn) {
	if stmt.Expr == "" {
		return
	}
	sources := a.analyzeEmbeddedExpr(stmt.Expr)
	a.returnResults = append(a.returnResults, []base.SourceColumnSet{sources})
}

func (a *plpgsqlAnalyzer) handleReturnNext(stmt *plpgsqlast.PLReturnNext) {
	if stmt.Expr == "" {
		return
	}
	sources := a.analyzeEmbeddedExpr(stmt.Expr)
	a.returnResults = append(a.returnResults, []base.SourceColumnSet{sources})
}

func (a *plpgsqlAnalyzer) handleExecSQL(stmt *plpgsqlast.PLExecSQL) {
	stmts, err := ParsePg(stmt.SQLText)
	if err != nil || len(stmts) != 1 {
		return
	}
	var results []base.SourceColumnSet
	if _, ok := stmts[0].AST.(*ast.SelectStmt); ok {
		results = a.analyzeEmbeddedSQL(stmt.SQLText)
	} else {
		// The analyzer reads SELECT alone, so another statement, which runs for
		// its effect, has its conditions and RETURNING list matched by name.
		accesses := a.extractor.accessTablesOf(stmt.SQLText)
		a.extractor.collectFallbackPredicateColumns(stmts[0].AST, accesses)
		results = a.extractor.returningLineage(stmts[0].AST, accesses)
	}
	for i, varName := range stmt.Into {
		if i < len(results) {
			a.scope.merge(varName, results[i])
		}
	}
}

// handleDynExecute analyzes EXECUTE of a constant query like the statement it
// runs. A query built at run time cannot be analyzed.
func (a *plpgsqlAnalyzer) handleDynExecute(stmt *plpgsqlast.PLDynExecute) {
	stmts, err := ParsePg("SELECT " + stmt.Query)
	if err != nil || len(stmts) != 1 {
		return
	}
	sel, ok := stmts[0].AST.(*ast.SelectStmt)
	if !ok || sel.TargetList == nil || len(sel.TargetList.Items) != 1 {
		return
	}
	rt, ok := sel.TargetList.Items[0].(*ast.ResTarget)
	if !ok {
		return
	}
	query, ok := constantString(rt.Val)
	if !ok {
		return
	}
	a.handleExecSQL(&plpgsqlast.PLExecSQL{SQLText: query, Into: stmt.Into})
}

// constantString returns the text of a string literal, a cast of one, or a
// concatenation of them.
func constantString(node ast.Node) (string, bool) {
	switch v := node.(type) {
	case *ast.A_Const:
		if s, ok := v.Val.(*ast.String); ok {
			return s.Str, true
		}
	case *ast.TypeCast:
		return constantString(v.Arg)
	case *ast.A_Expr:
		if names := astStrings(v.Name); len(names) == 1 && names[0] == "||" {
			left, ok := constantString(v.Lexpr)
			if !ok {
				return "", false
			}
			right, ok := constantString(v.Rexpr)
			if !ok {
				return "", false
			}
			return left + right, true
		}
	default:
	}
	return "", false
}

func (a *plpgsqlAnalyzer) handleForS(stmt *plpgsqlast.PLForS) {
	results := a.analyzeEmbeddedSQL(stmt.Query)
	merged := make(base.SourceColumnSet)
	for _, colSet := range results {
		for k, v := range colSet {
			merged[k] = v
		}
	}
	a.scope.merge(stmt.Var, merged)
	for _, s := range stmt.Body {
		a.walkStmt(s)
	}
}

func (a *plpgsqlAnalyzer) handleIf(stmt *plpgsqlast.PLIf) {
	a.handleCondition(stmt.Condition)
	for _, s := range stmt.ThenBody {
		a.walkStmt(s)
	}
	for _, elsif := range stmt.ElsIfs {
		if ei, ok := elsif.(*plpgsqlast.PLElsIf); ok {
			a.handleCondition(ei.Condition)
			for _, s := range ei.Body {
				a.walkStmt(s)
			}
		}
	}
	for _, s := range stmt.ElseBody {
		a.walkStmt(s)
	}
}

func (a *plpgsqlAnalyzer) handleCase(stmt *plpgsqlast.PLCase) {
	a.handleCondition(stmt.TestExpr)
	for _, when := range stmt.Whens {
		if cw, ok := when.(*plpgsqlast.PLCaseWhen); ok {
			a.handleCondition(cw.Expr)
			for _, s := range cw.Body {
				a.walkStmt(s)
			}
		}
	}
	for _, s := range stmt.ElseBody {
		a.walkStmt(s)
	}
}

func (a *plpgsqlAnalyzer) analyzeEmbeddedSQL(sql string) []base.SourceColumnSet {
	substituted := a.substituteVariables(sql)

	// Always collect access tables from embedded SQL for the top-level QuerySpan,
	// regardless of whether full analysis succeeds.
	accesses := a.collectAccessTablesFromSQL(substituted)

	stmts, err := ParsePg(substituted)
	if err != nil {
		return nil
	}
	if len(stmts) == 0 {
		return nil
	}

	selStmt, ok := stmts[0].AST.(*ast.SelectStmt)
	if !ok {
		return nil
	}

	query, err := a.extractor.analyzeSelect(selStmt)
	if err != nil {
		// When full analysis fails (e.g., type mismatches with aggregate functions),
		// fall back to extracting column references from the parse tree and resolving
		// them against known tables in the catalog.
		a.extractor.collectFallbackPredicateColumns(selStmt, accesses)
		return a.fallbackExtractLineage(sql, selStmt)
	}

	a.extractor.collectStatementPredicateColumns(query, selStmt, accesses)

	results := a.extractor.extractFuncLineage(query)

	// Map back variable references.
	origSelectItems := extractSelectItemNames(sql)
	for i, colSet := range results {
		if len(colSet) == 0 && i < len(origSelectItems) {
			varName := strings.TrimSpace(origSelectItems[i])
			if sources, ok := a.scope.get(varName); ok {
				results[i] = sources
			}
		}
	}

	return results
}

func extractSelectItemNames(sql string) []string {
	upper := strings.ToUpper(strings.TrimSpace(sql))
	idx := strings.Index(upper, "SELECT")
	if idx < 0 {
		return nil
	}
	rest := sql[idx+6:]

	fromIdx := -1
	depth := 0
	upperRest := strings.ToUpper(rest)
	for i := 0; i < len(upperRest); i++ {
		switch upperRest[i] {
		case '(':
			depth++
		case ')':
			depth--
		default:
			if depth == 0 && i+4 <= len(upperRest) && upperRest[i:i+4] == "FROM" {
				if (i == 0 || !isWordChar(rest[i-1])) && (i+4 >= len(rest) || !isWordChar(rest[i+4])) {
					fromIdx = i
				}
			}
		}
		if fromIdx >= 0 {
			break
		}
	}

	targetList := rest
	if fromIdx >= 0 {
		targetList = rest[:fromIdx]
	}

	var items []string
	depth = 0
	start := 0
	for i := 0; i < len(targetList); i++ {
		switch targetList[i] {
		case '(':
			depth++
		case ')':
			depth--
		case ',':
			if depth == 0 {
				items = append(items, strings.TrimSpace(targetList[start:i]))
				start = i + 1
			}
		default:
		}
	}
	items = append(items, strings.TrimSpace(targetList[start:]))

	return items
}

func (a *plpgsqlAnalyzer) analyzeEmbeddedExpr(expr string) base.SourceColumnSet {
	results := a.analyzeEmbeddedSQL("SELECT " + expr)
	merged := make(base.SourceColumnSet)
	for _, colSet := range results {
		for k, v := range colSet {
			merged[k] = v
		}
	}
	if len(merged) == 0 {
		if stmts, err := ParsePg("SELECT " + expr); err == nil && len(stmts) == 1 {
			mergeSourceColumnSetInto(merged, a.scopeSources(stmts[0].AST))
		}
	}
	return merged
}

func (a *plpgsqlAnalyzer) substituteVariables(sql string) string {
	stmts, err := ParsePg(sql)
	if err == nil && len(stmts) > 0 {
		if selStmt, ok := stmts[0].AST.(*ast.SelectStmt); ok {
			if _, err := a.extractor.analyzeSelect(selStmt); err == nil {
				return sql
			}
		}
	}

	result := sql
	for scope := a.scope; scope != nil; scope = scope.parent {
		for varName := range scope.vars {
			result = replaceWholeWord(result, varName, "NULL::text")
		}
	}

	return result
}

func replaceWholeWord(s, old, replacement string) string {
	lower := strings.ToLower(s)
	oldLower := strings.ToLower(old)
	var result strings.Builder
	i := 0
	for i < len(lower) {
		idx := strings.Index(lower[i:], oldLower)
		if idx < 0 {
			result.WriteString(s[i:])
			break
		}
		pos := i + idx
		if pos > 0 && isWordChar(s[pos-1]) {
			result.WriteString(s[i : pos+len(old)])
			i = pos + len(old)
			continue
		}
		end := pos + len(old)
		if end < len(s) && isWordChar(s[end]) {
			result.WriteString(s[i : pos+len(old)])
			i = pos + len(old)
			continue
		}
		result.WriteString(s[i:pos])
		result.WriteString(replacement)
		i = end
	}
	return result.String()
}

func isWordChar(b byte) bool {
	return (b >= 'a' && b <= 'z') || (b >= 'A' && b <= 'Z') || (b >= '0' && b <= '9') || b == '_'
}

func extractBaseVarName(target string) string {
	for i, c := range target {
		if c == '.' || c == '[' {
			return target[:i]
		}
	}
	return target
}

// collectAccessTablesFromSQL extracts all table/column references from embedded SQL,
// adds them to the extractor's funcSourceColumns, and returns them. This works even
// when AnalyzeSelectStmt fails, because it uses the AST-level ExtractAccessTables.
func (a *plpgsqlAnalyzer) collectAccessTablesFromSQL(sql string) base.SourceColumnSet {
	accesses := a.extractor.accessTablesOf(sql)
	for resource := range accesses {
		a.extractor.funcSourceColumns[resource] = true
	}
	return accesses
}

// accessTablesOf returns the tables sql reads, or none when it cannot tell.
func (e *omniQuerySpanExtractor) accessTablesOf(sql string) base.SourceColumnSet {
	accesses := make(base.SourceColumnSet)
	accessTables, err := ExtractAccessTables(sql, ExtractAccessTablesOption{
		DefaultDatabase:        e.defaultDatabase,
		DefaultSchema:          e.searchPath[0],
		SearchPath:             e.searchPath,
		GetDatabaseMetadata:    e.gCtx.GetDatabaseMetadataFunc,
		Ctx:                    e.ctx,
		InstanceID:             e.gCtx.InstanceID,
		SkipMetadataValidation: false,
	})
	if err != nil {
		return accesses
	}
	for _, resource := range accessTables {
		accesses[resource] = true
	}
	return accesses
}

func (a *plpgsqlAnalyzer) mergeReturnResults(nCols int) []base.SourceColumnSet {
	result := make([]base.SourceColumnSet, nCols)
	for i := range result {
		result[i] = make(base.SourceColumnSet)
	}

	for _, returnCols := range a.returnResults {
		for i := 0; i < nCols && i < len(returnCols); i++ {
			for k, v := range returnCols[i] {
				result[i][k] = v
			}
		}
	}

	return result
}

// fallbackExtractLineage is called when AnalyzeSelectStmt fails for embedded SQL
// (e.g., due to type mismatches with aggregate functions). It uses the parse tree
// to extract column references and resolves them against known tables and variables.
func (a *plpgsqlAnalyzer) fallbackExtractLineage(origSQL string, selStmt *ast.SelectStmt) []base.SourceColumnSet {
	if selStmt == nil || selStmt.TargetList == nil {
		return nil
	}

	// Collect table references from the FROM clause. The explicit-schema
	// markers are scoped to this statement — a previous fallback query's
	// qualified FROM must not pin a later query's unqualified reference.
	a.qualifiedFrom = make(map[string]bool)
	fromTables := a.collectFromTables(selStmt)

	var results []base.SourceColumnSet
	origItems := extractSelectItemNames(origSQL)

	for i, item := range selStmt.TargetList.Items {
		rt, ok := item.(*ast.ResTarget)
		if !ok {
			results = append(results, make(base.SourceColumnSet))
			continue
		}

		colSet := make(base.SourceColumnSet)

		// Try to extract column references from the expression.
		a.extractColumnRefsFromExpr(rt.Val, fromTables, colSet)

		// If still empty, try the original item name as a variable reference.
		if len(colSet) == 0 && i < len(origItems) {
			varName := strings.TrimSpace(origItems[i])
			// Strip wrapping parentheses for subquery expressions.
			varName = strings.TrimPrefix(strings.TrimSuffix(varName, ")"), "(")
			varName = strings.TrimSpace(varName)
			if sources, ok := a.scope.get(varName); ok {
				for k, v := range sources {
					colSet[k] = v
				}
			}
		}

		results = append(results, colSet)
	}

	// Extract column refs from WHERE clause for predicate tracking.
	if selStmt.WhereClause != nil {
		whereColSet := make(base.SourceColumnSet)
		a.extractColumnRefsFromExpr(selStmt.WhereClause, fromTables, whereColSet)
		for k, v := range whereColSet {
			a.extractor.predicateColumns[k] = v
		}
	}

	return results
}

// collectFromTables collects table references from the FROM clause and maps
// table names/aliases to their schema-qualified names.
func (a *plpgsqlAnalyzer) collectFromTables(selStmt *ast.SelectStmt) map[string]base.ColumnResource {
	tables := make(map[string]base.ColumnResource)
	if selStmt.FromClause == nil {
		return tables
	}

	for _, item := range selStmt.FromClause.Items {
		a.collectTablesFromNode(item, tables)
	}
	return tables
}

// resolveFallbackRelation resolves a textual fallback resource against the
// catalog. Unqualified FROM items default to "public" in collectTablesFromNode,
// so on a miss the extractor's search path is probed the way PostgreSQL
// would resolve the name.
// pushMarkerScope opens a nested explicit-qualification scope seeded from
// the current one, so markers collected inside a subquery or CTE apply to
// that scope's resolution but never leak outward. The returned restore
// function reinstates the caller's scope; the returned map is the nested
// scope for selective exports.
func (a *plpgsqlAnalyzer) pushMarkerScope() (func(), map[string]bool) {
	outer := a.qualifiedFrom
	nested := make(map[string]bool, len(outer))
	for k, v := range outer {
		nested[k] = v
	}
	a.qualifiedFrom = nested
	return func() { a.qualifiedFrom = outer }, nested
}

func (a *plpgsqlAnalyzer) resolveFallbackRelation(fromKey, schemaName, tableName string) *catalog.Relation {
	// collectTablesFromNode defaults unqualified FROM items to "public"; for
	// those (and only those — explicitly qualified items resolve exactly),
	// the configured search path decides resolution order, exactly like
	// PostgreSQL. The literal public lookup remains the last resort for
	// search paths that do not contain public.
	if schemaName == "public" && !a.qualifiedFrom[fromKey] {
		for _, pathSchema := range a.extractor.searchPath {
			if rel := a.extractor.cat.GetRelation(pathSchema, tableName); rel != nil {
				return rel
			}
		}
	}
	return a.extractor.cat.GetRelation(schemaName, tableName)
}

func (a *plpgsqlAnalyzer) collectTablesFromNode(node ast.Node, tables map[string]base.ColumnResource) {
	switch v := node.(type) {
	case *ast.RangeVar:
		schema := "public"
		if v.Schemaname != "" {
			schema = v.Schemaname
		}
		resource := base.ColumnResource{
			Database: a.extractor.defaultDatabase,
			Schema:   schema,
			Table:    v.Relname,
		}
		// The newest FROM item owns its key's qualification marker in this
		// scope: set it when explicitly qualified, clear any inherited one
		// when not — an inner unqualified FROM must not be pinned by a
		// same-named outer explicit FROM.
		if a.qualifiedFrom == nil {
			a.qualifiedFrom = make(map[string]bool)
		}
		tables[strings.ToLower(v.Relname)] = resource
		if v.Schemaname != "" {
			a.qualifiedFrom[strings.ToLower(v.Relname)] = true
		} else {
			delete(a.qualifiedFrom, strings.ToLower(v.Relname))
		}
		if v.Alias != nil && v.Alias.Aliasname != "" {
			tables[strings.ToLower(v.Alias.Aliasname)] = resource
			if v.Schemaname != "" {
				a.qualifiedFrom[strings.ToLower(v.Alias.Aliasname)] = true
			} else {
				delete(a.qualifiedFrom, strings.ToLower(v.Alias.Aliasname))
			}
		}
	case *ast.RangeSubselect:
		// For subquery aliases like (SELECT * FROM t) result, collect inner tables
		// and map them under the alias so column refs can be resolved.
		if v.Subquery != nil {
			if subSel, ok := v.Subquery.(*ast.SelectStmt); ok {
				restore, nested := a.pushMarkerScope()
				innerTables := a.collectFromTables(subSel)
				restore()
				if a.qualifiedFrom == nil {
					a.qualifiedFrom = make(map[string]bool)
				}
				// Add inner tables to the outer fromTables. Every key this
				// branch writes takes ownership of its qualification marker:
				// set from the borrowed resource's inner marker, cleared
				// otherwise — never inherited from the outer scope.
				for k, res := range innerTables {
					if _, exists := tables[k]; !exists {
						tables[k] = res
						if nested[k] {
							a.qualifiedFrom[k] = true
						} else {
							delete(a.qualifiedFrom, k)
						}
					}
				}
				// If the subquery has an alias, also map all inner tables'
				// columns as accessible through the alias.
				if v.Alias != nil && v.Alias.Aliasname != "" {
					alias := strings.ToLower(v.Alias.Aliasname)
					for k, res := range innerTables {
						tables[alias] = res
						if nested[k] {
							a.qualifiedFrom[alias] = true
						} else {
							delete(a.qualifiedFrom, alias)
						}
						break
					}
				}
			}
		}
	case *ast.JoinExpr:
		if v.Larg != nil {
			a.collectTablesFromNode(v.Larg, tables)
		}
		if v.Rarg != nil {
			a.collectTablesFromNode(v.Rarg, tables)
		}
	default:
	}
}

// extractColumnRefsFromExpr recursively walks an AST expression and resolves
// column references against known tables.
func (a *plpgsqlAnalyzer) extractColumnRefsFromExpr(node ast.Node, fromTables map[string]base.ColumnResource, result base.SourceColumnSet) {
	if node == nil {
		return
	}

	switch v := node.(type) {
	case *ast.ColumnRef:
		a.resolveColumnRef(v, fromTables, result)
	case *ast.FuncCall:
		if v.Args != nil {
			for _, arg := range v.Args.Items {
				a.extractColumnRefsFromExpr(arg, fromTables, result)
			}
		}
		// FILTER (WHERE ...) clause on aggregates → predicate columns.
		if v.AggFilter != nil {
			filterColSet := make(base.SourceColumnSet)
			a.extractColumnRefsFromExpr(v.AggFilter, fromTables, filterColSet)
			for k, val := range filterColSet {
				a.extractor.predicateColumns[k] = val
			}
		}
	case *ast.A_Expr:
		a.extractColumnRefsFromExpr(v.Lexpr, fromTables, result)
		a.extractColumnRefsFromExpr(v.Rexpr, fromTables, result)
	case *ast.SubLink:
		if v.Subselect != nil {
			if subSel, ok := v.Subselect.(*ast.SelectStmt); ok {
				// The subquery's qualification markers apply only within its
				// own resolution scope.
				restore, _ := a.pushMarkerScope()
				defer restore()
				subTables := a.collectFromTables(subSel)
				for k, val := range fromTables {
					if _, exists := subTables[k]; !exists {
						subTables[k] = val
					}
				}
				if subSel.TargetList != nil {
					for _, item := range subSel.TargetList.Items {
						if rt, ok := item.(*ast.ResTarget); ok {
							a.extractColumnRefsFromExpr(rt.Val, subTables, result)
						}
					}
				}
				// Also collect from subquery WHERE clause for predicate tracking.
				if subSel.WhereClause != nil {
					whereColSet := make(base.SourceColumnSet)
					a.extractColumnRefsFromExpr(subSel.WhereClause, subTables, whereColSet)
					for k, val := range whereColSet {
						a.extractor.predicateColumns[k] = val
					}
				}
			}
		}
	case *ast.TypeCast:
		a.extractColumnRefsFromExpr(v.Arg, fromTables, result)
	case *ast.BoolExpr:
		if v.Args != nil {
			for _, arg := range v.Args.Items {
				a.extractColumnRefsFromExpr(arg, fromTables, result)
			}
		}
	case *ast.CaseExpr:
		a.extractColumnRefsFromExpr(v.Arg, fromTables, result)
		if v.Args != nil {
			for _, w := range v.Args.Items {
				a.extractColumnRefsFromExpr(w, fromTables, result)
			}
		}
		a.extractColumnRefsFromExpr(v.Defresult, fromTables, result)
	case *ast.CaseWhen:
		a.extractColumnRefsFromExpr(v.Expr, fromTables, result)
		a.extractColumnRefsFromExpr(v.Result, fromTables, result)
	case *ast.CoalesceExpr:
		if v.Args != nil {
			for _, arg := range v.Args.Items {
				a.extractColumnRefsFromExpr(arg, fromTables, result)
			}
		}
	case *ast.NullTest:
		a.extractColumnRefsFromExpr(v.Arg, fromTables, result)
	case *ast.BooleanTest:
		a.extractColumnRefsFromExpr(v.Arg, fromTables, result)
	case *ast.A_Indirection:
		// Array subscript or field selection — the source is the base expression.
		a.extractColumnRefsFromExpr(v.Arg, fromTables, result)
		if v.Indirection != nil {
			for _, ind := range v.Indirection.Items {
				a.extractColumnRefsFromExpr(ind, fromTables, result)
			}
		}
	case *ast.JsonObjectConstructor:
		if v.Exprs != nil {
			for _, item := range v.Exprs.Items {
				if kv, ok := item.(*ast.JsonKeyValue); ok {
					if kv.Value != nil {
						a.extractColumnRefsFromExpr(kv.Value.RawExpr, fromTables, result)
					}
				}
			}
		}
	case *ast.JsonArrayConstructor:
		if v.Exprs != nil {
			for _, item := range v.Exprs.Items {
				if jve, ok := item.(*ast.JsonValueExpr); ok {
					a.extractColumnRefsFromExpr(jve.RawExpr, fromTables, result)
				}
			}
		}
	case *ast.JsonValueExpr:
		a.extractColumnRefsFromExpr(v.RawExpr, fromTables, result)
	case *ast.List:
		for _, item := range v.Items {
			a.extractColumnRefsFromExpr(item, fromTables, result)
		}
	default:
	}
}

// resolveColumnRef resolves a ColumnRef to a source column using known tables.
// If the table is a CTE, it traces through the CTE to find real source columns.
func (a *plpgsqlAnalyzer) resolveColumnRef(cr *ast.ColumnRef, fromTables map[string]base.ColumnResource, result base.SourceColumnSet) {
	if cr == nil || cr.Fields == nil || len(cr.Fields.Items) == 0 {
		return
	}

	var parts []string
	for _, f := range cr.Fields.Items {
		if s, ok := f.(*ast.String); ok {
			parts = append(parts, s.Str)
		}
	}

	switch len(parts) {
	case 1:
		colName := parts[0]
		if _, ok := a.scope.get(colName); ok {
			return
		}
		// Check if it's a column name in any FROM table.
		for fromKey, resource := range fromTables {
			rel := a.resolveFallbackRelation(fromKey, resource.Schema, resource.Table)
			// Standalone composite types are not FROM-able.
			if rel != nil && rel.RelKind != 'c' && relationHasColumn(rel, colName) {
				// Emit the schema the relation actually resolved to — an
				// unqualified item may have resolved through the search
				// path, not the public default.
				emitSchema, emitTable := resource.Schema, resource.Table
				if rel.Schema != nil {
					emitSchema, emitTable = rel.Schema.Name, rel.Name
				}
				result[base.ColumnResource{
					Database: resource.Database,
					Schema:   emitSchema,
					Table:    emitTable,
					Column:   colName,
				}] = true
				return
			}
		}
		// Check if it's a whole-row reference (table alias used as value, e.g., to_jsonb(t1)).
		if resource, ok := fromTables[strings.ToLower(colName)]; ok {
			rel := a.resolveFallbackRelation(strings.ToLower(colName), resource.Schema, resource.Table)
			if rel != nil && rel.RelKind != 'c' {
				emitSchema, emitTable := resource.Schema, resource.Table
				if rel.Schema != nil {
					emitSchema, emitTable = rel.Schema.Name, rel.Name
				}
				for _, col := range rel.Columns {
					result[base.ColumnResource{
						Database: resource.Database,
						Schema:   emitSchema,
						Table:    emitTable,
						Column:   col.Name,
					}] = true
				}
				return
			}
		}
	case 2:
		tableName := strings.ToLower(parts[0])
		colName := parts[1]
		if resource, ok := fromTables[tableName]; ok {
			// Check if this table is actually a CTE — trace through to real sources.
			// The CTE name is the original table name (resource.Table), not the alias.
			if a.cteMap != nil {
				if cteSel, isCTE := a.cteMap[strings.ToLower(resource.Table)]; isCTE {
					a.resolveThroughCTE(cteSel, colName, fromTables, result)
					return
				}
			}
			// A known standalone composite type is not FROM-able; suppress
			// lineage for it (unknown relations keep the textual fallback);
			// a resolved relation supplies the schema it actually lives in.
			rel := a.resolveFallbackRelation(tableName, resource.Schema, resource.Table)
			if rel != nil && rel.RelKind == 'c' {
				return
			}
			emitSchema, emitTable := resource.Schema, resource.Table
			if rel != nil && rel.Schema != nil {
				emitSchema, emitTable = rel.Schema.Name, rel.Name
			}
			result[base.ColumnResource{
				Database: resource.Database,
				Schema:   emitSchema,
				Table:    emitTable,
				Column:   colName,
			}] = true
		}
	default:
	}
}

// resolveThroughCTE traces a column reference through a CTE to find real source columns.
func (a *plpgsqlAnalyzer) resolveThroughCTE(cteSel *ast.SelectStmt, colName string, _ map[string]base.ColumnResource, result base.SourceColumnSet) {
	if cteSel == nil || cteSel.TargetList == nil {
		return
	}
	key := cteResolveKey{
		sel: cteSel,
		col: strings.ToLower(colName),
	}
	if a.resolvingCTE == nil {
		a.resolvingCTE = make(map[cteResolveKey]bool)
	}
	if a.resolvingCTE[key] {
		return
	}
	a.resolvingCTE[key] = true
	defer delete(a.resolvingCTE, key)

	// Build FROM tables for the CTE's query; its qualification markers are
	// scoped to this resolution.
	restoreMarkers, _ := a.pushMarkerScope()
	defer restoreMarkers()
	cteTables := a.collectFromTables(cteSel)
	// Include parent CTEs for nested CTE references.
	if a.cteMap != nil {
		for name := range a.cteMap {
			if _, exists := cteTables[name]; !exists {
				cteTables[name] = base.ColumnResource{
					Database: a.extractor.defaultDatabase,
					Schema:   "public",
					Table:    name,
				}
			}
		}
	}

	// Find the target entry matching the column name.
	for _, item := range cteSel.TargetList.Items {
		rt, ok := item.(*ast.ResTarget)
		if !ok {
			continue
		}
		// Match by alias first, then by expression name.
		rtName := rt.Name
		if rtName == "" {
			rtName = figureResTargetName(rt)
		}
		if !strings.EqualFold(rtName, colName) {
			continue
		}
		// Found matching column — extract source refs from its expression.
		a.extractColumnRefsFromExpr(rt.Val, cteTables, result)

		// Also collect predicate columns from the CTE's WHERE clause.
		if cteSel.WhereClause != nil {
			whereColSet := make(base.SourceColumnSet)
			a.extractColumnRefsFromExpr(cteSel.WhereClause, cteTables, whereColSet)
			for k, v := range whereColSet {
				a.extractor.predicateColumns[k] = v
			}
		}
		return
	}
}

// collectCTEDefinitions extracts CTE names and their SelectStmt definitions from a query.
func collectCTEDefinitions(selStmt *ast.SelectStmt) map[string]*ast.SelectStmt {
	if selStmt == nil || selStmt.WithClause == nil {
		return nil
	}

	cteMap := make(map[string]*ast.SelectStmt)
	for _, item := range selStmt.WithClause.Ctes.Items {
		cte, ok := item.(*ast.CommonTableExpr)
		if !ok {
			continue
		}
		if sel, ok := cte.Ctequery.(*ast.SelectStmt); ok {
			cteMap[strings.ToLower(cte.Ctename)] = sel
		}
	}
	return cteMap
}

// relationHasColumn checks if a catalog relation has a column with the given name.
func relationHasColumn(rel *catalog.Relation, colName string) bool {
	lowerName := strings.ToLower(colName)
	for _, col := range rel.Columns {
		if strings.ToLower(col.Name) == lowerName {
			return true
		}
	}
	return false
}