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