Skip to content

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

20.2 KB
Raw Blame
package pg

import (
	"strings"

	"github.com/bytebase/omni/pg/ast"
	"github.com/bytebase/omni/pg/catalog"

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

// collectPredicateColumns records the columns that decide which rows q and
// every query nested in it return: those read by WHERE, JOIN ON, HAVING, and
// aggregate FILTER conditions, LIMIT and OFFSET, and the arguments of
// set-returning functions. The database evaluates conditions on unmasked values, so these columns
// decide which rows come back even when their values are masked.
func (e *omniQuerySpanExtractor) collectPredicateColumns(q *catalog.Query) {
	e.collectPredicateColumnsInStack([]*catalog.Query{q}, make(map[*catalog.Query]bool))
}

// collectStatementPredicateColumns records the predicate columns of sel,
// analyzed as query, that reads accesses.
func (e *omniQuerySpanExtractor) collectStatementPredicateColumns(query *catalog.Query, sel *ast.SelectStmt, accesses base.SourceColumnSet) {
	e.collectPredicateColumns(query)
	// The analyzer leaves a set operation's LIMIT and OFFSET out of its tree,
	// so they are resolved by name.
	r := newPredicateNameResolver(sel, e.namedFunctionReturnsSet)
	limited := false
	ast.Inspect(sel, func(n ast.Node) bool {
		if v, ok := n.(*ast.SelectStmt); ok && v.Op != ast.SETOP_NONE {
			for _, limit := range []ast.Node{v.LimitCount, v.LimitOffset} {
				if limit != nil {
					r.addReferences(limit)
					e.analyzeFunctionsCalledIn(limit)
					limited = true
				}
			}
		}
		return true
	})
	if limited {
		e.recordPredicateNames(r, accesses)
	}
}

// collectDiscardedOutputColumns records the columns a SELECT whose rows are
// discarded reads in its output. It still evaluates the output, so those
// columns decide how long it takes. query is nil when sel failed analysis.
func (e *omniQuerySpanExtractor) collectDiscardedOutputColumns(query *catalog.Query, sel *ast.SelectStmt, accesses base.SourceColumnSet) {
	if query != nil {
		for _, set := range e.extractFuncLineage(query) {
			mergeSourceColumnSetInto(e.predicateColumns, set)
		}
		return
	}
	if sel.TargetList == nil {
		return
	}
	r := newPredicateNameResolver(sel, e.namedFunctionReturnsSet)
	r.addReferences(sel.TargetList)
	e.recordPredicateNames(r, accesses)
}

func (e *omniQuerySpanExtractor) collectPredicateColumnsInStack(queryStack []*catalog.Query, visited map[*catalog.Query]bool) {
	q := currentQuery(queryStack)
	if q == nil || visited[q] {
		return
	}
	visited[q] = true

	for _, cte := range q.CTEList {
		if cte != nil {
			e.collectPredicateColumnsInStack(appendQuery(queryStack, cte.Query), visited)
		}
	}
	e.collectConditionColumns(queryStack, q.LimitCount, visited)
	e.collectConditionColumns(queryStack, q.LimitOffset, visited)
	if q.SetOp != catalog.SetOpNone {
		// INTERSECT and EXCEPT keep a row by whether the other branch has it,
		// so their branches' output columns decide which rows come back.
		filters := q.SetOp == catalog.SetOpIntersect || q.SetOp == catalog.SetOpIntersectAll ||
			q.SetOp == catalog.SetOpExcept || q.SetOp == catalog.SetOpExceptAll
		for _, branch := range []*catalog.Query{q.LArg, q.RArg} {
			if filters && branch != nil {
				for _, te := range branch.TargetList {
					if te != nil && !te.ResJunk {
						e.walkExprWithVisited(appendQuery(queryStack, branch), te.Expr, e.predicateColumns, make(map[queryExprKey]bool))
					}
				}
			}
			e.collectPredicateColumnsInStack(appendQuery(queryStack, branch), visited)
		}
		return
	}
	for _, rte := range q.RangeTable {
		if rte == nil {
			continue
		}
		if rte.Kind == catalog.RTESubquery {
			e.collectPredicateColumnsInStack(appendQuery(queryStack, rte.Subquery), visited)
		}
		for _, expr := range rte.FuncExprs {
			// A function in FROM returns the rows its arguments and the
			// conditions in its body ask for.
			call, ok := expr.(*catalog.FuncCallExpr)
			if !ok {
				e.collectConditionColumns(queryStack, expr, visited)
				continue
			}
			for _, arg := range call.Args {
				e.collectConditionColumns(queryStack, arg, visited)
			}
			for _, proc := range e.userProcsCalled(call) {
				e.analyzeFunctionBody(proc)
			}
		}
	}
	if q.JoinTree != nil {
		e.collectConditionColumns(queryStack, q.JoinTree.Quals, visited)
		for _, node := range q.JoinTree.FromList {
			e.collectJoinConditionColumns(queryStack, node, visited)
		}
	}
	e.collectConditionColumns(queryStack, q.HavingQual, visited)
	for _, te := range q.TargetList {
		if te != nil {
			e.collectNestedPredicateColumns(queryStack, te.Expr, visited)
		}
	}
}

func (e *omniQuerySpanExtractor) collectJoinConditionColumns(queryStack []*catalog.Query, node catalog.JoinNode, visited map[*catalog.Query]bool) {
	join, ok := node.(*catalog.JoinExprNode)
	if !ok || join == nil {
		return
	}
	// The analyzer turns USING and NATURAL joins into equality quals.
	e.collectConditionColumns(queryStack, join.Quals, visited)
	e.collectJoinConditionColumns(queryStack, join.Left, visited)
	e.collectJoinConditionColumns(queryStack, join.Right, visited)
}

// collectConditionColumns records every column condition reads, including the
// output columns of its subqueries, and the conditions nested in it.
func (e *omniQuerySpanExtractor) collectConditionColumns(queryStack []*catalog.Query, condition catalog.AnalyzedExpr, visited map[*catalog.Query]bool) {
	if condition == nil {
		return
	}
	e.walkExprWithVisited(queryStack, condition, e.predicateColumns, make(map[queryExprKey]bool))
	e.collectNestedPredicateColumns(queryStack, condition, visited)
}

// collectNestedPredicateColumns records the conditions nested in expr: the
// FILTER of an aggregate or window function, the arguments of a set-returning
// function, which decide how many rows it returns, and the conditions of its
// subqueries.
func (e *omniQuerySpanExtractor) collectNestedPredicateColumns(queryStack []*catalog.Query, expr catalog.AnalyzedExpr, visited map[*catalog.Query]bool) {
	catalog.WalkAnalyzedExpr(expr, func(n catalog.AnalyzedExpr) bool {
		var inputs []catalog.AnalyzedExpr
		switch v := n.(type) {
		case *catalog.SubLinkExpr:
			if v.SubQuery != nil {
				e.collectPredicateColumnsInStack(appendQuery(queryStack, v.SubQuery), visited)
			}
		case *catalog.AggExpr:
			inputs = []catalog.AnalyzedExpr{v.AggFilter}
		case *catalog.WindowFuncExpr:
			inputs = []catalog.AnalyzedExpr{v.AggFilter}
		case *catalog.FuncCallExpr:
			if e.returnsSet(v.FuncOID) {
				inputs = v.Args
			}
		default:
		}
		for _, input := range inputs {
			if input != nil {
				e.walkExprWithVisited(queryStack, input, e.predicateColumns, make(map[queryExprKey]bool))
			}
		}
		return true
	})
}

// analyzeFunctionsCalledIn analyzes the body of every user function node calls,
// which merges the body's predicates, as walkExpr does for an analyzed call.
// Without argument types the overload is unknown, so every one of the name is
// analyzed.
func (e *omniQuerySpanExtractor) analyzeFunctionsCalledIn(node ast.Node) {
	ast.Inspect(node, func(n ast.Node) bool {
		if call, ok := n.(*ast.FuncCall); ok {
			for _, proc := range e.userProcsNamed(astStrings(call.Funcname)) {
				e.analyzeFunctionBody(proc)
			}
		}
		return true
	})
}

// userProcsCalled returns the user function an analyzed call invokes. An
// opaque call, which the analyzer could not match to a function (as for a
// stand-in), may invoke any user function of its name.
func (e *omniQuerySpanExtractor) userProcsCalled(call *catalog.FuncCallExpr) []*catalog.UserProc {
	if proc := e.cat.GetUserProcByOID(call.FuncOID); proc != nil {
		return []*catalog.UserProc{proc}
	}
	if call.FuncOID == 0 {
		return e.userProcsNamed([]string{call.FuncName})
	}
	return nil
}

// userProcsNamed returns every user function, overloads included, that a
// possibly schema-qualified name may call.
func (e *omniQuerySpanExtractor) userProcsNamed(names []string) []*catalog.UserProc {
	if len(names) == 0 {
		return nil
	}
	name := names[len(names)-1]
	schemas := e.searchPath
	if len(names) > 1 {
		schemas = []string{names[len(names)-2]}
	}
	var procs []*catalog.UserProc
	for _, schema := range schemas {
		for _, row := range e.cat.QueryPgProc(schema) {
			if strings.EqualFold(row.ProName, name) {
				if proc := e.cat.GetUserProcByOID(row.OID); proc != nil {
					procs = append(procs, proc)
				}
			}
		}
	}
	return procs
}

// namedFunctionReturnsSet reports whether a function of that name is known to
// return a set.
func (e *omniQuerySpanExtractor) namedFunctionReturnsSet(name string) bool {
	for _, proc := range e.userProcsNamed([]string{name}) {
		if proc.RetSet {
			return true
		}
	}
	for _, proc := range e.cat.LookupProcByName(strings.ToLower(name)) {
		if proc.RetSet {
			return true
		}
	}
	return false
}

// returnsSet reports whether the function is known to return a set. An
// unknown function, analyzed opaquely, is not.
func (e *omniQuerySpanExtractor) returnsSet(oid uint32) bool {
	if proc := e.cat.GetUserProcByOID(oid); proc != nil {
		return proc.RetSet
	}
	if proc := e.cat.LookupProcByOID(oid); proc != nil {
		return proc.RetSet
	}
	return false
}

// collectFallbackPredicateColumns stands in for collectPredicateColumns when
// analysis fails. Without scopes it over-approximates by name, so that an
// analysis failure never lets a condition on a masked column through.
func (e *omniQuerySpanExtractor) collectFallbackPredicateColumns(stmt ast.Node, accesses base.SourceColumnSet) {
	e.analyzeFunctionsCalledIn(stmt)
	r := newPredicateNameResolver(stmt, e.namedFunctionReturnsSet)
	for _, name := range r.usingNames {
		r.addName(name)
	}
	for _, condition := range r.conditions {
		r.addReferences(condition)
	}
	// The joined columns are unknown without scopes, so a NATURAL JOIN reads
	// every column of both sides.
	for _, join := range r.naturalJoins {
		r.addJoinedRelation(join.Larg)
		r.addJoinedRelation(join.Rarg)
	}
	for _, setOperation := range r.filteringSetOperations {
		r.addSetOperationOutputs(setOperation)
	}
	e.recordPredicateNames(r, accesses)
}

func (e *omniQuerySpanExtractor) recordPredicateNames(r *predicateNameResolver, accesses base.SourceColumnSet) {
	mergeSourceColumnSetInto(e.predicateColumns, e.columnsNamed(r, accesses))
}

// columnsNamed returns the columns of accesses that r's names match.
func (e *omniQuerySpanExtractor) columnsNamed(r *predicateNameResolver, accesses base.SourceColumnSet) base.SourceColumnSet {
	columns := make(base.SourceColumnSet)
	for resource := range accesses {
		rel := e.cat.GetRelation(resource.Schema, resource.Table)
		if rel == nil {
			continue
		}
		table := strings.ToLower(resource.Table)
		for _, column := range rel.Columns {
			name := strings.ToLower(column.Name)
			if r.wholeRows[table] || r.anyTable[name] || r.ofTable[table][name] {
				columns[base.ColumnResource{
					Database: resource.Database,
					Schema:   resource.Schema,
					Table:    resource.Table,
					Column:   column.Name,
				}] = true
			}
		}
	}
	return columns
}

// returningLineage returns, for each column a DML statement's RETURNING list
// outputs, the columns of accesses it reads, matched by name. It returns nil
// for a statement without RETURNING.
func (e *omniQuerySpanExtractor) returningLineage(stmt ast.Node, accesses base.SourceColumnSet) []base.SourceColumnSet {
	var returning *ast.List
	var target *ast.RangeVar
	switch v := stmt.(type) {
	case *ast.InsertStmt:
		returning, target = v.ReturningList, v.Relation
	case *ast.UpdateStmt:
		returning, target = v.ReturningList, v.Relation
	case *ast.DeleteStmt:
		returning, target = v.ReturningList, v.Relation
	default:
	}
	if returning == nil {
		return nil
	}
	var lineage []base.SourceColumnSet
	for _, item := range returning.Items {
		rt, ok := item.(*ast.ResTarget)
		if !ok {
			continue
		}
		if isStarTarget(rt) && target != nil {
			// RETURNING * outputs every column of the target table in order.
			for resource := range accesses {
				if !strings.EqualFold(resource.Table, target.Relname) {
					continue
				}
				if rel := e.cat.GetRelation(resource.Schema, resource.Table); rel != nil {
					for _, column := range rel.Columns {
						lineage = append(lineage, base.SourceColumnSet{{
							Database: resource.Database,
							Schema:   resource.Schema,
							Table:    resource.Table,
							Column:   column.Name,
						}: true})
					}
				}
				break
			}
			continue
		}
		r := newPredicateNameResolver(stmt, e.namedFunctionReturnsSet)
		r.addReferences(rt.Val)
		lineage = append(lineage, e.columnsNamed(r, accesses))
	}
	return lineage
}

// predicateNameResolver resolves the column references of conditions by name.
// A reference qualified by a table or its alias matches that table's column;
// any other reference matches the same-named column of every table, and an
// output name of a subquery or CTE also reads the columns that produce it.
type predicateNameResolver struct {
	// The WHERE (of SELECT, UPDATE, and DELETE), JOIN ON, HAVING, and FILTER
	// conditions, LIMIT and OFFSET,
	// arguments of FROM and set-returning functions, USING column names,
	// NATURAL joins, and INTERSECT and EXCEPT operations of the statement, at
	// any depth.
	conditions             []ast.Node
	usingNames             []string
	naturalJoins           []*ast.JoinExpr
	filteringSetOperations []*ast.SelectStmt
	// projections maps an output name to the expressions that produce it. A
	// subquery or CTE name maps to its whole query, so a whole-row reference
	// to it reads every column.
	projections map[string][]ast.Node
	// relations maps a name or alias in FROM to the relations it may name; an
	// alias reused across scopes names several.
	relations map[string]map[string]bool
	// derived holds the names of subqueries and CTEs.
	derived map[string]bool

	anyTable  map[string]bool
	ofTable   map[string]map[string]bool
	wholeRows map[string]bool
}

func newPredicateNameResolver(stmt ast.Node, returnsSet func(name string) bool) *predicateNameResolver {
	r := &predicateNameResolver{
		projections: make(map[string][]ast.Node),
		relations:   make(map[string]map[string]bool),
		derived:     make(map[string]bool),
		anyTable:    make(map[string]bool),
		ofTable:     make(map[string]map[string]bool),
		wholeRows:   make(map[string]bool),
	}
	project := func(name string, nodes ...ast.Node) {
		if name != "" {
			r.projections[strings.ToLower(name)] = append(r.projections[strings.ToLower(name)], nodes...)
		}
	}
	ast.Inspect(stmt, func(n ast.Node) bool {
		switch v := n.(type) {
		case *ast.SelectStmt:
			r.conditions = append(r.conditions, v.WhereClause, v.HavingClause, v.LimitCount, v.LimitOffset)
			if v.Op == ast.SETOP_INTERSECT || v.Op == ast.SETOP_EXCEPT {
				r.filteringSetOperations = append(r.filteringSetOperations, v)
			}
			if v.TargetList != nil {
				for _, item := range v.TargetList.Items {
					if rt, ok := item.(*ast.ResTarget); ok {
						name := rt.Name
						if name == "" {
							name = figureResTargetName(rt)
						}
						project(name, rt.Val)
					}
				}
			}
		case *ast.UpdateStmt:
			r.conditions = append(r.conditions, v.WhereClause)
		case *ast.DeleteStmt:
			r.conditions = append(r.conditions, v.WhereClause)
		case *ast.JoinExpr:
			r.conditions = append(r.conditions, v.Quals)
			r.usingNames = append(r.usingNames, astStrings(v.UsingClause)...)
			if v.IsNatural {
				r.naturalJoins = append(r.naturalJoins, v)
			}
		case *ast.FuncCall:
			r.conditions = append(r.conditions, v.AggFilter)
			if names := astStrings(v.Funcname); len(names) > 0 && returnsSet(names[len(names)-1]) {
				r.conditions = append(r.conditions, v.Args)
			}
		case *ast.RangeFunction:
			// A function in FROM returns the rows its arguments ask for.
			r.conditions = append(r.conditions, v.Functions)
		case *ast.CommonTableExpr:
			r.derived[strings.ToLower(v.Ctename)] = true
			project(v.Ctename, v.Ctequery)
			for i, name := range astStrings(v.Aliascolnames) {
				project(name, outputsAt(v.Ctequery, i)...)
			}
		case *ast.RangeSubselect:
			if v.Alias != nil {
				r.derived[strings.ToLower(v.Alias.Aliasname)] = true
				project(v.Alias.Aliasname, v.Subquery)
				for i, name := range astStrings(v.Alias.Colnames) {
					project(name, outputsAt(v.Subquery, i)...)
				}
			}
		case *ast.RangeVar:
			relation := strings.ToLower(v.Relname)
			r.addRelationName(relation, relation)
			if v.Alias != nil {
				r.addRelationName(v.Alias.Aliasname, relation)
			}
		default:
		}
		return true
	})
	return r
}

func (r *predicateNameResolver) addRelationName(name, relation string) {
	name = strings.ToLower(name)
	if name == "" {
		return
	}
	if r.relations[name] == nil {
		r.relations[name] = make(map[string]bool)
	}
	r.relations[name][relation] = true
}

// relationsNamed returns the tables name may refer to, and the subqueries or
// CTEs it may refer to instead.
func (r *predicateNameResolver) relationsNamed(name string) (map[string]bool, []string) {
	name = strings.ToLower(name)
	tables := make(map[string]bool)
	var derived []string
	if r.derived[name] {
		derived = append(derived, name)
	}
	for relation := range r.relations[name] {
		if r.derived[relation] {
			derived = append(derived, relation)
		} else {
			tables[relation] = true
		}
	}
	return tables, derived
}

// addSetOperationOutputs adds the outputs of every branch of sel, which an
// INTERSECT or EXCEPT compares.
func (r *predicateNameResolver) addSetOperationOutputs(sel *ast.SelectStmt) {
	if sel == nil {
		return
	}
	if sel.Op != ast.SETOP_NONE {
		r.addSetOperationOutputs(sel.Larg)
		r.addSetOperationOutputs(sel.Rarg)
		return
	}
	if sel.TargetList == nil {
		return
	}
	for _, item := range sel.TargetList.Items {
		rt, ok := item.(*ast.ResTarget)
		if !ok {
			continue
		}
		if !isStarTarget(rt) {
			r.addReferences(rt.Val)
			continue
		}
		if sel.FromClause != nil {
			for _, from := range sel.FromClause.Items {
				r.addJoinedRelation(from)
			}
		}
	}
}

func (r *predicateNameResolver) addJoinedRelation(node ast.Node) {
	switch v := node.(type) {
	case *ast.RangeVar:
		if v.Alias != nil && v.Alias.Aliasname != "" {
			r.addWholeRow(v.Alias.Aliasname)
		} else {
			r.addWholeRow(v.Relname)
		}
	case *ast.RangeSubselect:
		r.addReferences(v.Subquery)
	case *ast.JoinExpr:
		r.addJoinedRelation(v.Larg)
		r.addJoinedRelation(v.Rarg)
	default:
	}
}

func (r *predicateNameResolver) addReferences(node ast.Node) {
	ast.Inspect(node, func(n ast.Node) bool {
		if ref, ok := n.(*ast.ColumnRef); ok {
			r.addReference(ref)
		}
		return true
	})
}

func (r *predicateNameResolver) addReference(ref *ast.ColumnRef) {
	if ref.Fields == nil {
		return
	}
	var fields []string
	star := false
	for _, field := range ref.Fields.Items {
		switch v := field.(type) {
		case *ast.String:
			fields = append(fields, v.Str)
		case *ast.A_Star:
			star = true
		default:
		}
	}
	if len(fields) == 0 {
		return
	}
	last := fields[len(fields)-1]
	// t.* reads every column of t; a bare t may be a column or a whole-row
	// reference.
	if star || len(fields) == 1 {
		r.addWholeRow(last)
		return
	}
	tables, derived := r.relationsNamed(fields[len(fields)-2])
	for table := range tables {
		if r.ofTable[table] == nil {
			r.ofTable[table] = make(map[string]bool)
		}
		r.ofTable[table][strings.ToLower(last)] = true
	}
	if len(derived) > 0 || len(tables) == 0 {
		r.addName(last)
	}
}

func (r *predicateNameResolver) addWholeRow(name string) {
	tables, derived := r.relationsNamed(name)
	for table := range tables {
		r.wholeRows[table] = true
	}
	for _, relation := range derived {
		r.addName(relation)
	}
	r.addName(name)
}

func (r *predicateNameResolver) addName(name string) {
	name = strings.ToLower(name)
	if name == "" || r.anyTable[name] {
		return
	}
	r.anyTable[name] = true
	for _, projection := range r.projections[name] {
		r.addReferences(projection)
	}
}

// outputsAt returns the expressions that produce the i-th output column of
// query, or query itself when they cannot be told apart.
func outputsAt(query ast.Node, i int) []ast.Node {
	sel, ok := query.(*ast.SelectStmt)
	if !ok || sel == nil {
		return []ast.Node{query}
	}
	if sel.Op != ast.SETOP_NONE {
		return append(outputsAt(sel.Larg, i), outputsAt(sel.Rarg, i)...)
	}
	if sel.TargetList == nil || i >= len(sel.TargetList.Items) {
		return []ast.Node{query}
	}
	for _, item := range sel.TargetList.Items[:i+1] {
		if rt, ok := item.(*ast.ResTarget); !ok || isStarTarget(rt) {
			return []ast.Node{query}
		}
	}
	return []ast.Node{sel.TargetList.Items[i].(*ast.ResTarget).Val}
}

func astStrings(list *ast.List) []string {
	if list == nil {
		return nil
	}
	var result []string
	for _, item := range list.Items {
		if s, ok := item.(*ast.String); ok {
			result = append(result, s.Str)
		}
	}
	return result
}