structural.go

Documentation: cuelang.org/go/internal/core/subsume

     1  // Copyright 2020 CUE Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package subsume
    16  
    17  // TODO: structural subsumption has not yet been implemented.
    18  
    19  import "cuelang.org/go/internal/core/adt"
    20  
    21  func (s *subsumer) subsumes(gt, lt adt.Conjunct) bool {
    22  	if gt == lt {
    23  		return true
    24  	}
    25  
    26  	// First try evaluating at the value level.
    27  	x, _ := gt.Expr().(adt.Value)
    28  	y, _ := lt.Expr().(adt.Value)
    29  	if x == nil {
    30  		// Fall back to structural.
    31  		return s.structural(gt, lt)
    32  	}
    33  	if y == nil {
    34  		return false
    35  	}
    36  
    37  	return s.values(x, y)
    38  }
    39  
    40  func (s *subsumer) conjunct(gt, lt adt.Conjunct) bool {
    41  	return false
    42  }
    43  
    44  func (s *subsumer) c(env *adt.Environment, x adt.Expr) adt.Conjunct {
    45  	return adt.MakeRootConjunct(env, x)
    46  }
    47  
    48  func isBottomConjunct(c adt.Conjunct) bool {
    49  	b, _ := c.Expr().(*adt.Bottom)
    50  	return b != nil
    51  }
    52  
    53  func (s *subsumer) node(env *adt.Environment, up int32) *adt.Vertex {
    54  	for ; up != 0; up-- {
    55  		env = env.Up
    56  	}
    57  	return env.Vertex
    58  }
    59  
    60  func (s *subsumer) structural(a, b adt.Conjunct) bool {
    61  	if isBottomConjunct(b) {
    62  		return true
    63  	}
    64  
    65  	switch x := a.Expr().(type) {
    66  	case *adt.DisjunctionExpr:
    67  
    68  	case *adt.StructLit:
    69  	case *adt.ListLit:
    70  
    71  	case *adt.FieldReference:
    72  		if y, ok := b.Elem().(*adt.FieldReference); ok && x.Label == y.Label {
    73  			if s.node(a.Env, x.UpCount) == s.node(b.Env, y.UpCount) {
    74  				return true
    75  			}
    76  		}
    77  
    78  	case *adt.LabelReference:
    79  		if y, ok := b.Elem().(*adt.LabelReference); ok {
    80  			if s.node(a.Env, x.UpCount) == s.node(b.Env, y.UpCount) {
    81  				return true
    82  			}
    83  		}
    84  
    85  	case *adt.DynamicReference:
    86  		if y, ok := b.Elem().(*adt.FieldReference); ok {
    87  			if s.node(a.Env, x.UpCount) == s.node(b.Env, y.UpCount) {
    88  				return true
    89  			}
    90  		}
    91  
    92  	case *adt.ImportReference:
    93  		if y, ok := b.Elem().(*adt.ImportReference); ok &&
    94  			x.ImportPath == y.ImportPath {
    95  			return true
    96  		}
    97  
    98  	case *adt.LetReference:
    99  		if y, ok := b.Elem().(*adt.LetReference); ok && x.Label == y.Label {
   100  			if s.node(a.Env, x.UpCount) == s.node(b.Env, y.UpCount) {
   101  				return true
   102  			}
   103  		}
   104  
   105  	case *adt.SelectorExpr:
   106  		if y, ok := a.Elem().(*adt.SelectorExpr); ok &&
   107  			x.Sel == y.Sel &&
   108  			s.conjunct(s.c(a.Env, x.X), s.c(b.Env, y.X)) {
   109  			return true
   110  		}
   111  
   112  	case *adt.IndexExpr:
   113  		if y, ok := b.Elem().(*adt.IndexExpr); ok &&
   114  			s.conjunct(s.c(a.Env, x.X), s.c(b.Env, y.X)) &&
   115  			s.conjunct(s.c(a.Env, x.Index), s.c(b.Env, y.Index)) {
   116  			return true
   117  		}
   118  
   119  	case *adt.SliceExpr:
   120  		if r, ok := b.Elem().(*adt.SliceExpr); ok &&
   121  			s.conjunct(s.c(a.Env, x.X), s.c(b.Env, r.X)) &&
   122  			s.conjunct(s.c(a.Env, x.Lo), s.c(b.Env, r.Lo)) &&
   123  			s.conjunct(s.c(a.Env, x.Hi), s.c(b.Env, r.Hi)) {
   124  			return true
   125  		}
   126  
   127  	case *adt.Interpolation:
   128  		switch y := b.Elem().(type) {
   129  		case *adt.String:
   130  			// Be conservative if not ground.
   131  			s.inexact = true
   132  
   133  		case *adt.Interpolation:
   134  			// structural equivalence
   135  			if len(x.Parts) != len(y.Parts) {
   136  				return false
   137  			}
   138  			for i, p := range x.Parts {
   139  				if !s.conjunct(s.c(a.Env, p), s.c(b.Env, y.Parts[i])) {
   140  					return false
   141  				}
   142  			}
   143  			return true
   144  		}
   145  
   146  	case *adt.BoundExpr:
   147  		if y, ok := b.Elem().(*adt.BoundExpr); ok && x.Op == y.Op {
   148  			return s.conjunct(s.c(a.Env, x.Expr), s.c(b.Env, y.Expr))
   149  		}
   150  
   151  	case *adt.UnaryExpr:
   152  		if y, ok := b.Elem().(*adt.UnaryExpr); ok && x.Op == y.Op {
   153  			return s.conjunct(s.c(a.Env, x.X), s.c(b.Env, y.X))
   154  		}
   155  
   156  	case *adt.BinaryExpr:
   157  		if y, ok := b.Elem().(*adt.BinaryExpr); ok && x.Op == y.Op {
   158  			return s.conjunct(s.c(a.Env, x.X), s.c(b.Env, y.X)) &&
   159  				s.conjunct(s.c(a.Env, x.Y), s.c(b.Env, y.Y))
   160  		}
   161  
   162  	case *adt.CallExpr:
   163  		if y, ok := b.Elem().(*adt.CallExpr); ok {
   164  			if len(x.Args) != len(y.Args) {
   165  				return false
   166  			}
   167  			for i, arg := range x.Args {
   168  				if !s.conjunct(s.c(a.Env, arg), s.c(b.Env, y.Args[i])) {
   169  					return false
   170  				}
   171  			}
   172  			return s.conjunct(s.c(a.Env, x.Fun), s.c(b.Env, y.Fun))
   173  		}
   174  	}
   175  	return false
   176  }
   177  
   178  func (s *subsumer) structLit(
   179  	ea *adt.Environment, sa *adt.StructLit,
   180  	eb *adt.Environment, sb *adt.StructLit) bool {
   181  
   182  	// Create index of instance fields.
   183  	ca := newCollatedDecls()
   184  	ca.collate(ea, sa)
   185  
   186  	if ca.yielders != nil || ca.dynamic != nil {
   187  		// TODO: we could do structural comparison of comprehensions
   188  		// in many cases. For instance, an if clause would subsume
   189  		// structurally if it subsumes any of the if clauses in sb.
   190  		s.inexact = true
   191  		return false
   192  	}
   193  
   194  	cb := newCollatedDecls()
   195  	cb.collate(eb, sb)
   196  
   197  	if ca.hasOptional && !s.IgnoreOptional {
   198  		// TODO: same argument here as for comprehensions. This could
   199  		// be made to work.
   200  		if ca.pattern != nil || ca.dynamic != nil {
   201  			s.inexact = true
   202  			return false
   203  		}
   204  
   205  		// for f, b := range cb.fields {
   206  		// 	if !b.required || f.IsDef() {
   207  		// 		continue
   208  		// 	}
   209  		// 	name := ctx.LabelStr(b.Label)
   210  		// 	arg := &stringLit{x.baseValue, name, nil}
   211  		// 	u, _ := x.optionals.constraint(ctx, arg)
   212  		// 	if u != nil && !s.subsumes(u, b.v) {
   213  		// 		return false
   214  		// 	}
   215  		// }
   216  
   217  	}
   218  
   219  	return false
   220  
   221  }
   222  
   223  // collatedDecls is used to compute the structural subsumption of two
   224  // struct literals.
   225  type collatedDecls struct {
   226  	fields      map[adt.Feature]field
   227  	yielders    []adt.Yielder
   228  	pattern     []*adt.BulkOptionalField
   229  	dynamic     []*adt.DynamicField
   230  	values      []adt.Expr
   231  	additional  []*adt.Ellipsis
   232  	isOpen      bool
   233  	hasOptional bool
   234  }
   235  
   236  func newCollatedDecls() *collatedDecls {
   237  	return &collatedDecls{fields: map[adt.Feature]field{}}
   238  }
   239  
   240  type field struct {
   241  	required  bool
   242  	conjuncts []adt.Conjunct
   243  }
   244  
   245  func (c *collatedDecls) collate(env *adt.Environment, s *adt.StructLit) {
   246  	for _, d := range s.Decls {
   247  		switch x := d.(type) {
   248  		case *adt.Field:
   249  			e := c.fields[x.Label]
   250  			e.required = true
   251  			e.conjuncts = append(e.conjuncts, adt.MakeRootConjunct(env, x))
   252  			c.fields[x.Label] = e
   253  			if x.ArcType != adt.ArcMember {
   254  				c.hasOptional = true
   255  			}
   256  
   257  		case *adt.BulkOptionalField:
   258  			c.pattern = append(c.pattern, x)
   259  			c.hasOptional = true
   260  
   261  		case *adt.DynamicField:
   262  			c.dynamic = append(c.dynamic, x)
   263  			c.hasOptional = true
   264  
   265  		case *adt.Ellipsis:
   266  			c.isOpen = true
   267  			c.additional = append(c.additional, x)
   268  
   269  		case *adt.Comprehension:
   270  			c.yielders = append(c.yielders, x.Clauses...)
   271  
   272  		case *adt.LetClause:
   273  			c.yielders = append(c.yielders, x)
   274  		}
   275  	}
   276  }
   277
View as plain text