1// Copyright 2015 The Prometheus Authors 2// Licensed under the Apache License, Version 2.0 (the "License"); 3// you may not use this file except in compliance with the License. 4// You may obtain a copy of the License at 5// 6// http://www.apache.org/licenses/LICENSE-2.0 7// 8// Unless required by applicable law or agreed to in writing, software 9// distributed under the License is distributed on an "AS IS" BASIS, 10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11// See the License for the specific language governing permissions and 12// limitations under the License. 13//nolint //Since this was copied from Prometheus leave it as is 14package promql 15 16import ( 17 "fmt" 18 "time" 19 20 "github.com/prometheus/prometheus/pkg/labels" 21 "github.com/prometheus/prometheus/storage" 22) 23 24// Node is a generic interface for all nodes in an AST. 25// 26// Whenever numerous nodes are listed such as in a switch-case statement 27// or a chain of function definitions (e.g. String(), expr(), etc.) convention is 28// to list them as follows: 29// 30// - Statements 31// - statement types (alphabetical) 32// - ... 33// - Expressions 34// - expression types (alphabetical) 35// - ... 36// 37type Node interface { 38 // String representation of the node that returns the given node when parsed 39 // as part of a valid query. 40 String() string 41} 42 43// Statement is a generic interface for all statements. 44type Statement interface { 45 Node 46 47 // stmt ensures that no other type accidentally implements the interface 48 stmt() 49} 50 51// Statements is a list of statement nodes that implements Node. 52type Statements []Statement 53 54// AlertStmt represents an added alert rule. 55type AlertStmt struct { 56 Name string 57 Expr Expr 58 Duration time.Duration 59 Labels labels.Labels 60 Annotations labels.Labels 61} 62 63// EvalStmt holds an expression and information on the range it should 64// be evaluated on. 65type EvalStmt struct { 66 Expr Expr // Expression to be evaluated. 67 68 // The time boundaries for the evaluation. If Start equals End an instant 69 // is evaluated. 70 Start, End time.Time 71 // Time between two evaluated instants for the range [Start:End]. 72 Interval time.Duration 73} 74 75// RecordStmt represents an added recording rule. 76type RecordStmt struct { 77 Name string 78 Expr Expr 79 Labels labels.Labels 80} 81 82func (*AlertStmt) stmt() {} 83func (*EvalStmt) stmt() {} 84func (*RecordStmt) stmt() {} 85 86// Expr is a generic interface for all expression types. 87type Expr interface { 88 Node 89 90 // Type returns the type the expression evaluates to. It does not perform 91 // in-depth checks as this is done at parsing-time. 92 Type() ValueType 93 // expr ensures that no other types accidentally implement the interface. 94 expr() 95} 96 97// Expressions is a list of expression nodes that implements Node. 98type Expressions []Expr 99 100// AggregateExpr represents an aggregation operation on a Vector. 101type AggregateExpr struct { 102 Op ItemType // The used aggregation operation. 103 Expr Expr // The Vector expression over which is aggregated. 104 Param Expr // Parameter used by some aggregators. 105 Grouping []string // The labels by which to group the Vector. 106 Without bool // Whether to drop the given labels rather than keep them. 107} 108 109// BinaryExpr represents a binary expression between two child expressions. 110type BinaryExpr struct { 111 Op ItemType // The operation of the expression. 112 LHS, RHS Expr // The operands on the respective sides of the operator. 113 114 // The matching behavior for the operation if both operands are Vectors. 115 // If they are not this field is nil. 116 VectorMatching *VectorMatching 117 118 // If a comparison operator, return 0/1 rather than filtering. 119 ReturnBool bool 120} 121 122// Call represents a function call. 123type Call struct { 124 Func *Function // The function that was called. 125 Args Expressions // Arguments used in the call. 126} 127 128// MatrixSelector represents a Matrix selection. 129type MatrixSelector struct { 130 Name string 131 Range time.Duration 132 Offset time.Duration 133 LabelMatchers []*labels.Matcher 134 135 // The series are populated at query preparation time. 136 series []storage.Series 137} 138 139// NumberLiteral represents a number. 140type NumberLiteral struct { 141 Val float64 142} 143 144// ParenExpr wraps an expression so it cannot be disassembled as a consequence 145// of operator precedence. 146type ParenExpr struct { 147 Expr Expr 148} 149 150// StringLiteral represents a string. 151type StringLiteral struct { 152 Val string 153} 154 155// UnaryExpr represents a unary operation on another expression. 156// Currently unary operations are only supported for Scalars. 157type UnaryExpr struct { 158 Op ItemType 159 Expr Expr 160} 161 162// VectorSelector represents a Vector selection. 163type VectorSelector struct { 164 Name string 165 Offset time.Duration 166 LabelMatchers []*labels.Matcher 167 168 // The series are populated at query preparation time. 169 series []storage.Series 170} 171 172func (e *AggregateExpr) Type() ValueType { return ValueTypeVector } 173func (e *Call) Type() ValueType { return e.Func.ReturnType } 174func (e *MatrixSelector) Type() ValueType { return ValueTypeMatrix } 175func (e *NumberLiteral) Type() ValueType { return ValueTypeScalar } 176func (e *ParenExpr) Type() ValueType { return e.Expr.Type() } 177func (e *StringLiteral) Type() ValueType { return ValueTypeString } 178func (e *UnaryExpr) Type() ValueType { return e.Expr.Type() } 179func (e *VectorSelector) Type() ValueType { return ValueTypeVector } 180func (e *BinaryExpr) Type() ValueType { 181 if e.LHS.Type() == ValueTypeScalar && e.RHS.Type() == ValueTypeScalar { 182 return ValueTypeScalar 183 } 184 return ValueTypeVector 185} 186 187func (*AggregateExpr) expr() {} 188func (*BinaryExpr) expr() {} 189func (*Call) expr() {} 190func (*MatrixSelector) expr() {} 191func (*NumberLiteral) expr() {} 192func (*ParenExpr) expr() {} 193func (*StringLiteral) expr() {} 194func (*UnaryExpr) expr() {} 195func (*VectorSelector) expr() {} 196 197// VectorMatchCardinality describes the cardinality relationship 198// of two Vectors in a binary operation. 199type VectorMatchCardinality int 200 201const ( 202 CardOneToOne VectorMatchCardinality = iota 203 CardManyToOne 204 CardOneToMany 205 CardManyToMany 206) 207 208func (vmc VectorMatchCardinality) String() string { 209 switch vmc { 210 case CardOneToOne: 211 return "one-to-one" 212 case CardManyToOne: 213 return "many-to-one" 214 case CardOneToMany: 215 return "one-to-many" 216 case CardManyToMany: 217 return "many-to-many" 218 } 219 panic("promql.VectorMatchCardinality.String: unknown match cardinality") 220} 221 222// VectorMatching describes how elements from two Vectors in a binary 223// operation are supposed to be matched. 224type VectorMatching struct { 225 // The cardinality of the two Vectors. 226 Card VectorMatchCardinality 227 // MatchingLabels contains the labels which define equality of a pair of 228 // elements from the Vectors. 229 MatchingLabels []string 230 // On includes the given label names from matching, 231 // rather than excluding them. 232 On bool 233 // Include contains additional labels that should be included in 234 // the result from the side with the lower cardinality. 235 Include []string 236} 237 238// Visitor allows visiting a Node and its child nodes. The Visit method is 239// invoked for each node with the path leading to the node provided additionally. 240// If the result visitor w is not nil and no error, Walk visits each of the children 241// of node with the visitor w, followed by a call of w.Visit(nil, nil). 242type Visitor interface { 243 Visit(node Node, path []Node) (w Visitor, err error) 244} 245 246// Walk traverses an AST in depth-first order: It starts by calling 247// v.Visit(node, path); node must not be nil. If the visitor w returned by 248// v.Visit(node, path) is not nil and the visitor returns no error, Walk is 249// invoked recursively with visitor w for each of the non-nil children of node, 250// followed by a call of w.Visit(nil), returning an error 251// As the tree is descended the path of previous nodes is provided. 252func Walk(v Visitor, node Node, path []Node) error { 253 var err error 254 if v, err = v.Visit(node, path); v == nil || err != nil { 255 return err 256 } 257 path = append(path, node) 258 259 switch n := node.(type) { 260 case Statements: 261 for _, s := range n { 262 if err := Walk(v, s, path); err != nil { 263 return err 264 } 265 } 266 case *AlertStmt: 267 if err := Walk(v, n.Expr, path); err != nil { 268 return err 269 } 270 271 case *EvalStmt: 272 if err := Walk(v, n.Expr, path); err != nil { 273 return err 274 } 275 276 case *RecordStmt: 277 if err := Walk(v, n.Expr, path); err != nil { 278 return err 279 } 280 281 case Expressions: 282 for _, e := range n { 283 if err := Walk(v, e, path); err != nil { 284 return err 285 } 286 } 287 case *AggregateExpr: 288 if err := Walk(v, n.Expr, path); err != nil { 289 return err 290 } 291 292 case *BinaryExpr: 293 if err := Walk(v, n.LHS, path); err != nil { 294 return err 295 } 296 if err := Walk(v, n.RHS, path); err != nil { 297 return err 298 } 299 300 case *Call: 301 if err := Walk(v, n.Args, path); err != nil { 302 return err 303 } 304 305 case *ParenExpr: 306 if err := Walk(v, n.Expr, path); err != nil { 307 return err 308 } 309 310 case *UnaryExpr: 311 if err := Walk(v, n.Expr, path); err != nil { 312 return err 313 } 314 315 case *MatrixSelector, *NumberLiteral, *StringLiteral, *VectorSelector: 316 // nothing to do 317 318 default: 319 panic(fmt.Errorf("promql.Walk: unhandled node type %T", node)) 320 } 321 322 _, err = v.Visit(nil, nil) 323 return err 324} 325 326type inspector func(Node, []Node) error 327 328func (f inspector) Visit(node Node, path []Node) (Visitor, error) { 329 if err := f(node, path); err == nil { 330 return f, nil 331 } else { 332 return nil, err 333 } 334} 335 336// Inspect traverses an AST in depth-first order: It starts by calling 337// f(node, path); node must not be nil. If f returns a nil error, Inspect invokes f 338// for all the non-nil children of node, recursively. 339func Inspect(node Node, f inspector) { 340 Walk(inspector(f), node, nil) 341} 342