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