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 14package parser 15 16import ( 17 "context" 18 "time" 19 20 "github.com/pkg/errors" 21 22 "github.com/prometheus/prometheus/pkg/labels" 23 "github.com/prometheus/prometheus/storage" 24) 25 26// Node is a generic interface for all nodes in an AST. 27// 28// Whenever numerous nodes are listed such as in a switch-case statement 29// or a chain of function definitions (e.g. String(), PromQLExpr(), etc.) convention is 30// to list them as follows: 31// 32// - Statements 33// - statement types (alphabetical) 34// - ... 35// - Expressions 36// - expression types (alphabetical) 37// - ... 38// 39type Node interface { 40 // String representation of the node that returns the given node when parsed 41 // as part of a valid query. 42 String() string 43 44 // PositionRange returns the position of the AST Node in the query string. 45 PositionRange() PositionRange 46} 47 48// Statement is a generic interface for all statements. 49type Statement interface { 50 Node 51 52 // PromQLStmt ensures that no other type accidentally implements the interface 53 // nolint:unused 54 PromQLStmt() 55} 56 57// EvalStmt holds an expression and information on the range it should 58// be evaluated on. 59type EvalStmt struct { 60 Expr Expr // Expression to be evaluated. 61 62 // The time boundaries for the evaluation. If Start equals End an instant 63 // is evaluated. 64 Start, End time.Time 65 // Time between two evaluated instants for the range [Start:End]. 66 Interval time.Duration 67} 68 69func (*EvalStmt) PromQLStmt() {} 70 71// Expr is a generic interface for all expression types. 72type Expr interface { 73 Node 74 75 // Type returns the type the expression evaluates to. It does not perform 76 // in-depth checks as this is done at parsing-time. 77 Type() ValueType 78 // PromQLExpr ensures that no other types accidentally implement the interface. 79 PromQLExpr() 80} 81 82// Expressions is a list of expression nodes that implements Node. 83type Expressions []Expr 84 85// AggregateExpr represents an aggregation operation on a Vector. 86type AggregateExpr struct { 87 Op ItemType // The used aggregation operation. 88 Expr Expr // The Vector expression over which is aggregated. 89 Param Expr // Parameter used by some aggregators. 90 Grouping []string // The labels by which to group the Vector. 91 Without bool // Whether to drop the given labels rather than keep them. 92 PosRange PositionRange 93} 94 95// BinaryExpr represents a binary expression between two child expressions. 96type BinaryExpr struct { 97 Op ItemType // The operation of the expression. 98 LHS, RHS Expr // The operands on the respective sides of the operator. 99 100 // The matching behavior for the operation if both operands are Vectors. 101 // If they are not this field is nil. 102 VectorMatching *VectorMatching 103 104 // If a comparison operator, return 0/1 rather than filtering. 105 ReturnBool bool 106} 107 108// Call represents a function call. 109type Call struct { 110 Func *Function // The function that was called. 111 Args Expressions // Arguments used in the call. 112 113 PosRange PositionRange 114} 115 116// MatrixSelector represents a Matrix selection. 117type MatrixSelector struct { 118 // It is safe to assume that this is an VectorSelector 119 // if the parser hasn't returned an error. 120 VectorSelector Expr 121 Range time.Duration 122 123 EndPos Pos 124} 125 126// SubqueryExpr represents a subquery. 127type SubqueryExpr struct { 128 Expr Expr 129 Range time.Duration 130 // OriginalOffset is the actual offset that was set in the query. 131 // This never changes. 132 OriginalOffset time.Duration 133 // Offset is the offset used during the query execution 134 // which is calculated using the original offset, at modifier time, 135 // eval time, and subquery offsets in the AST tree. 136 Offset time.Duration 137 Timestamp *int64 138 StartOrEnd ItemType // Set when @ is used with start() or end() 139 Step time.Duration 140 141 EndPos Pos 142} 143 144// NumberLiteral represents a number. 145type NumberLiteral struct { 146 Val float64 147 148 PosRange PositionRange 149} 150 151// ParenExpr wraps an expression so it cannot be disassembled as a consequence 152// of operator precedence. 153type ParenExpr struct { 154 Expr Expr 155 PosRange PositionRange 156} 157 158// StringLiteral represents a string. 159type StringLiteral struct { 160 Val string 161 PosRange PositionRange 162} 163 164// UnaryExpr represents a unary operation on another expression. 165// Currently unary operations are only supported for Scalars. 166type UnaryExpr struct { 167 Op ItemType 168 Expr Expr 169 170 StartPos Pos 171} 172 173// StepInvariantExpr represents a query which evaluates to the same result 174// irrespective of the evaluation time given the raw samples from TSDB remain unchanged. 175// Currently this is only used for engine optimisations and the parser does not produce this. 176type StepInvariantExpr struct { 177 Expr Expr 178} 179 180func (e *StepInvariantExpr) String() string { return e.Expr.String() } 181 182func (e *StepInvariantExpr) PositionRange() PositionRange { return e.Expr.PositionRange() } 183 184// VectorSelector represents a Vector selection. 185type VectorSelector struct { 186 Name string 187 // OriginalOffset is the actual offset that was set in the query. 188 // This never changes. 189 OriginalOffset time.Duration 190 // Offset is the offset used during the query execution 191 // which is calculated using the original offset, at modifier time, 192 // eval time, and subquery offsets in the AST tree. 193 Offset time.Duration 194 Timestamp *int64 195 StartOrEnd ItemType // Set when @ is used with start() or end() 196 LabelMatchers []*labels.Matcher 197 198 // The unexpanded seriesSet populated at query preparation time. 199 UnexpandedSeriesSet storage.SeriesSet 200 Series []storage.Series 201 202 PosRange PositionRange 203} 204 205// TestStmt is an internal helper statement that allows execution 206// of an arbitrary function during handling. It is used to test the Engine. 207type TestStmt func(context.Context) error 208 209func (TestStmt) String() string { return "test statement" } 210func (TestStmt) PromQLStmt() {} 211 212func (TestStmt) PositionRange() PositionRange { 213 return PositionRange{ 214 Start: -1, 215 End: -1, 216 } 217} 218func (e *AggregateExpr) Type() ValueType { return ValueTypeVector } 219func (e *Call) Type() ValueType { return e.Func.ReturnType } 220func (e *MatrixSelector) Type() ValueType { return ValueTypeMatrix } 221func (e *SubqueryExpr) Type() ValueType { return ValueTypeMatrix } 222func (e *NumberLiteral) Type() ValueType { return ValueTypeScalar } 223func (e *ParenExpr) Type() ValueType { return e.Expr.Type() } 224func (e *StringLiteral) Type() ValueType { return ValueTypeString } 225func (e *UnaryExpr) Type() ValueType { return e.Expr.Type() } 226func (e *VectorSelector) Type() ValueType { return ValueTypeVector } 227func (e *BinaryExpr) Type() ValueType { 228 if e.LHS.Type() == ValueTypeScalar && e.RHS.Type() == ValueTypeScalar { 229 return ValueTypeScalar 230 } 231 return ValueTypeVector 232} 233func (e *StepInvariantExpr) Type() ValueType { return e.Expr.Type() } 234 235func (*AggregateExpr) PromQLExpr() {} 236func (*BinaryExpr) PromQLExpr() {} 237func (*Call) PromQLExpr() {} 238func (*MatrixSelector) PromQLExpr() {} 239func (*SubqueryExpr) PromQLExpr() {} 240func (*NumberLiteral) PromQLExpr() {} 241func (*ParenExpr) PromQLExpr() {} 242func (*StringLiteral) PromQLExpr() {} 243func (*UnaryExpr) PromQLExpr() {} 244func (*VectorSelector) PromQLExpr() {} 245func (*StepInvariantExpr) PromQLExpr() {} 246 247// VectorMatchCardinality describes the cardinality relationship 248// of two Vectors in a binary operation. 249type VectorMatchCardinality int 250 251const ( 252 CardOneToOne VectorMatchCardinality = iota 253 CardManyToOne 254 CardOneToMany 255 CardManyToMany 256) 257 258func (vmc VectorMatchCardinality) String() string { 259 switch vmc { 260 case CardOneToOne: 261 return "one-to-one" 262 case CardManyToOne: 263 return "many-to-one" 264 case CardOneToMany: 265 return "one-to-many" 266 case CardManyToMany: 267 return "many-to-many" 268 } 269 panic("promql.VectorMatchCardinality.String: unknown match cardinality") 270} 271 272// VectorMatching describes how elements from two Vectors in a binary 273// operation are supposed to be matched. 274type VectorMatching struct { 275 // The cardinality of the two Vectors. 276 Card VectorMatchCardinality 277 // MatchingLabels contains the labels which define equality of a pair of 278 // elements from the Vectors. 279 MatchingLabels []string 280 // On includes the given label names from matching, 281 // rather than excluding them. 282 On bool 283 // Include contains additional labels that should be included in 284 // the result from the side with the lower cardinality. 285 Include []string 286} 287 288// Visitor allows visiting a Node and its child nodes. The Visit method is 289// invoked for each node with the path leading to the node provided additionally. 290// If the result visitor w is not nil and no error, Walk visits each of the children 291// of node with the visitor w, followed by a call of w.Visit(nil, nil). 292type Visitor interface { 293 Visit(node Node, path []Node) (w Visitor, err error) 294} 295 296// Walk traverses an AST in depth-first order: It starts by calling 297// v.Visit(node, path); node must not be nil. If the visitor w returned by 298// v.Visit(node, path) is not nil and the visitor returns no error, Walk is 299// invoked recursively with visitor w for each of the non-nil children of node, 300// followed by a call of w.Visit(nil), returning an error 301// As the tree is descended the path of previous nodes is provided. 302func Walk(v Visitor, node Node, path []Node) error { 303 var err error 304 if v, err = v.Visit(node, path); v == nil || err != nil { 305 return err 306 } 307 path = append(path, node) 308 309 for _, e := range Children(node) { 310 if err := Walk(v, e, path); err != nil { 311 return err 312 } 313 } 314 315 _, err = v.Visit(nil, nil) 316 return err 317} 318 319func ExtractSelectors(expr Expr) [][]*labels.Matcher { 320 var selectors [][]*labels.Matcher 321 Inspect(expr, func(node Node, _ []Node) error { 322 vs, ok := node.(*VectorSelector) 323 if ok { 324 selectors = append(selectors, vs.LabelMatchers) 325 } 326 return nil 327 }) 328 return selectors 329} 330 331type inspector func(Node, []Node) error 332 333func (f inspector) Visit(node Node, path []Node) (Visitor, error) { 334 if err := f(node, path); err != nil { 335 return nil, err 336 } 337 338 return f, nil 339} 340 341// Inspect traverses an AST in depth-first order: It starts by calling 342// f(node, path); node must not be nil. If f returns a nil error, Inspect invokes f 343// for all the non-nil children of node, recursively. 344func Inspect(node Node, f inspector) { 345 //nolint: errcheck 346 Walk(inspector(f), node, nil) 347} 348 349// Children returns a list of all child nodes of a syntax tree node. 350func Children(node Node) []Node { 351 // For some reasons these switches have significantly better performance than interfaces 352 switch n := node.(type) { 353 case *EvalStmt: 354 return []Node{n.Expr} 355 case Expressions: 356 // golang cannot convert slices of interfaces 357 ret := make([]Node, len(n)) 358 for i, e := range n { 359 ret[i] = e 360 } 361 return ret 362 case *AggregateExpr: 363 // While this does not look nice, it should avoid unnecessary allocations 364 // caused by slice resizing 365 if n.Expr == nil && n.Param == nil { 366 return nil 367 } else if n.Expr == nil { 368 return []Node{n.Param} 369 } else if n.Param == nil { 370 return []Node{n.Expr} 371 } else { 372 return []Node{n.Expr, n.Param} 373 } 374 case *BinaryExpr: 375 return []Node{n.LHS, n.RHS} 376 case *Call: 377 // golang cannot convert slices of interfaces 378 ret := make([]Node, len(n.Args)) 379 for i, e := range n.Args { 380 ret[i] = e 381 } 382 return ret 383 case *SubqueryExpr: 384 return []Node{n.Expr} 385 case *ParenExpr: 386 return []Node{n.Expr} 387 case *UnaryExpr: 388 return []Node{n.Expr} 389 case *MatrixSelector: 390 return []Node{n.VectorSelector} 391 case *StepInvariantExpr: 392 return []Node{n.Expr} 393 case *NumberLiteral, *StringLiteral, *VectorSelector: 394 // nothing to do 395 return []Node{} 396 default: 397 panic(errors.Errorf("promql.Children: unhandled node type %T", node)) 398 } 399} 400 401// PositionRange describes a position in the input string of the parser. 402type PositionRange struct { 403 Start Pos 404 End Pos 405} 406 407// mergeRanges is a helper function to merge the PositionRanges of two Nodes. 408// Note that the arguments must be in the same order as they 409// occur in the input string. 410func mergeRanges(first Node, last Node) PositionRange { 411 return PositionRange{ 412 Start: first.PositionRange().Start, 413 End: last.PositionRange().End, 414 } 415} 416 417// Item implements the Node interface. 418// This makes it possible to call mergeRanges on them. 419func (i *Item) PositionRange() PositionRange { 420 return PositionRange{ 421 Start: i.Pos, 422 End: i.Pos + Pos(len(i.Val)), 423 } 424} 425 426func (e *AggregateExpr) PositionRange() PositionRange { 427 return e.PosRange 428} 429func (e *BinaryExpr) PositionRange() PositionRange { 430 return mergeRanges(e.LHS, e.RHS) 431} 432func (e *Call) PositionRange() PositionRange { 433 return e.PosRange 434} 435func (e *EvalStmt) PositionRange() PositionRange { 436 return e.Expr.PositionRange() 437} 438func (e Expressions) PositionRange() PositionRange { 439 if len(e) == 0 { 440 // Position undefined. 441 return PositionRange{ 442 Start: -1, 443 End: -1, 444 } 445 } 446 return mergeRanges(e[0], e[len(e)-1]) 447} 448func (e *MatrixSelector) PositionRange() PositionRange { 449 return PositionRange{ 450 Start: e.VectorSelector.PositionRange().Start, 451 End: e.EndPos, 452 } 453} 454func (e *SubqueryExpr) PositionRange() PositionRange { 455 return PositionRange{ 456 Start: e.Expr.PositionRange().Start, 457 End: e.EndPos, 458 } 459} 460func (e *NumberLiteral) PositionRange() PositionRange { 461 return e.PosRange 462} 463func (e *ParenExpr) PositionRange() PositionRange { 464 return e.PosRange 465} 466func (e *StringLiteral) PositionRange() PositionRange { 467 return e.PosRange 468} 469func (e *UnaryExpr) PositionRange() PositionRange { 470 return PositionRange{ 471 Start: e.StartPos, 472 End: e.Expr.PositionRange().End, 473 } 474} 475func (e *VectorSelector) PositionRange() PositionRange { 476 return e.PosRange 477} 478