tidb expr_iterator 代码
文件路径：/planner/memo/expr_iterator.go
/ Copyright 2018 PingCAP, Inc.
/
/ Licensed under the Apache License, Version 2.0 (the "License");
/ you may not use this file except in compliance with the License.
/ You may obtain a copy of the License at
/
/ http://www.apache.org/licenses/LICENSE-2.0
/
/ Unless required by applicable law or agreed to in writing, software
/ distributed under the License is distributed on an "AS IS" BASIS,
/ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
/ See the License for the specific language governing permissions and
/ limitations under the License.
package memo
import (
"container/list"
)
/ ExprIter enumerates all the equivalent expressions in the Group according to
/ the expression pattern.
type ExprIter struct {
/ Group and Element solely identify a Group expression.
*Group
*list.Element
/ matched indicates whether the current Group expression bound by the
/ iterator matches the pattern after the creation or iteration.
matched bool
/ Pattern describes the node of pattern tree.
/ The Operand type of the Group expression and the EngineType of the Group
/ must be matched with it.
*Pattern
/ Children is used to iterate the child expressions.
Children []*ExprIter
}
/ Next returns the next Group expression matches the pattern.
func (iter *ExprIter) Next() (found bool) {
defer func() {
iter.matched = found
}()
/ Iterate child firstly.
for i := len(iter.Children) - 1; i >= 0; i-- {
if !iter.Children[i].Next() {
continue
}
for j := i + 1; j < len(iter.Children); j++ {
iter.Children[j].Reset()
}
return true
}
/ It's root node or leaf ANY node.
if iter.Group == nil || iter.Operand == OperandAny {
return false
}
/ Otherwise, iterate itself to find more matched equivalent expressions.
for elem := iter.Element.Next(); elem != nil; elem = elem.Next() {
expr := elem.Value.(*GroupExpr)
if !iter.Operand.Match(GetOperand(expr.ExprNode)) {
/ All the Equivalents which have the same Operand are continuously
/ stored in the list. Once the current equivalent can not Match
/ the Operand, the rest can not, either.
return false
}
if len(iter.Children) == 0 {
iter.Element = elem
return true
}
if len(iter.Children) != len(expr.Children) {
continue
}
allMatched := true
for i := range iter.Children {
iter.Children[i].Group = expr.Children[i]
if !iter.Children[i].Reset() {
allMatched = false
break
}
}
if allMatched {
iter.Element = elem
return true
}
}
return false
}
/ Matched returns whether the iterator founds a Group expression matches the
/ pattern.
func (iter *ExprIter) Matched() bool {
return iter.matched
}
/ Reset resets the iterator to the first matched Group expression.
func (iter *ExprIter) Reset() (findMatch bool) {
defer func() { iter.matched = findMatch }()
if iter.Pattern.MatchOperandAny(iter.Group.EngineType) {
return true
}
for elem := iter.Group.GetFirstElem(iter.Operand); elem != nil; elem = elem.Next() {
expr := elem.Value.(*GroupExpr)
if !iter.Pattern.Match(GetOperand(expr.ExprNode), expr.Group.EngineType) {
break
}
/ The leaf node of the pattern tree might not be an OperandAny or a XXXScan.
/ We allow the patterns like: Selection -> Projection.
/ For example, we have such a memo:
/ Group#1
/ Selection_0 input:[Group#2]
/ Group#2
/ Projection_1 input:[Group#3]
/ Projection_2 input:[Group#4]
/ Group#3
/ .....
/ For the pattern above, we will match it twice: `Selection_0->Projection_1`
/ and `Selection_0->Projection_2`. So if the iterator has no children, we can safely return
/ the element here.
if len(iter.Children) == 0 {
iter.Element = elem
return true
}
if len(expr.Children) != len(iter.Children) {
continue
}
allMatched := true
for i := range iter.Children {
iter.Children[i].Group = expr.Children[i]
if !iter.Children[i].Reset() {
allMatched = false
break
}
}
if allMatched {
iter.Element = elem
return true
}
}
return false
}
/ GetExpr returns the root GroupExpr of the iterator.
func (iter *ExprIter) GetExpr() *GroupExpr {
return iter.Element.Value.(*GroupExpr)
}
/ NewExprIterFromGroupElem creates the iterator on the Group Element.
func NewExprIterFromGroupElem(elem *list.Element, p *Pattern) *ExprIter {
expr := elem.Value.(*GroupExpr)
if !p.Match(GetOperand(expr.ExprNode), expr.Group.EngineType) {
return nil
}
iter := newExprIterFromGroupExpr(expr, p)
if iter != nil {
iter.Element = elem
}
return iter
}
/ newExprIterFromGroupExpr creates the iterator on the Group expression.
func newExprIterFromGroupExpr(expr *GroupExpr, p *Pattern) *ExprIter {
if len(p.Children) != 0 && len(p.Children) != len(expr.Children) {
return nil
}
iter := &ExprIter{Pattern: p, matched: true}
for i := range p.Children {
childIter := newExprIterFromGroup(expr.Children[i], p.Children[i])
if childIter == nil {
return nil
}
iter.Children = append(iter.Children, childIter)
}
return iter
}
/ newExprIterFromGroup creates the iterator on the Group.
func newExprIterFromGroup(g *Group, p *Pattern) *ExprIter {
if p.MatchOperandAny(g.EngineType) {
return &ExprIter{Group: g, Pattern: p, matched: true}
}
for elem := g.GetFirstElem(p.Operand); elem != nil; elem = elem.Next() {
expr := elem.Value.(*GroupExpr)
if !p.Match(GetOperand(expr.ExprNode), g.EngineType) {
return nil
}
iter := newExprIterFromGroupExpr(expr, p)
if iter != nil {
iter.Group, iter.Element = g, elem
return iter
}
}
return nil
}