vertex.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  import (
    18  	"fmt"
    19  
    20  	"cuelang.org/go/internal/core/adt"
    21  	"cuelang.org/go/internal/core/export"
    22  )
    23  
    24  // Notes:
    25  //   - Can optional fields of y can always be ignored here? Maybe not in the
    26  //     schema case.
    27  //   - Definitions of y can be ignored in data mode.
    28  //
    29  // TODO(perf): use merge sort where possible.
    30  func (s *subsumer) vertices(x, y *adt.Vertex) bool {
    31  	if x == y {
    32  		return true
    33  	}
    34  	if x.ArcType < y.ArcType {
    35  		return false
    36  	}
    37  
    38  	if s.Defaults {
    39  		y = y.Default()
    40  	}
    41  
    42  	if b, _ := y.BaseValue.(*adt.Bottom); b != nil {
    43  		// If the value is incomplete, the error is not final. So either check
    44  		// structural equivalence or return an error.
    45  		return !b.IsIncomplete()
    46  	}
    47  
    48  	ctx := s.ctx
    49  
    50  	final := y.IsData() || s.Final
    51  
    52  	switch v := x.BaseValue.(type) {
    53  	case *adt.Bottom:
    54  		return false
    55  
    56  	case *adt.ListMarker:
    57  		if !y.IsList() {
    58  			s.errf("list does not subsume %v (type %s)", y, y.Kind())
    59  			return false
    60  		}
    61  		if !s.listVertices(x, y) {
    62  			return false
    63  		}
    64  		// TODO: allow other arcs alongside list arc.
    65  		return true
    66  
    67  	case *adt.StructMarker:
    68  		_, ok := y.BaseValue.(*adt.StructMarker)
    69  		if !ok {
    70  			return false
    71  		}
    72  
    73  	case adt.Value:
    74  		if !s.values(v, y.Value()) {
    75  			return false
    76  		}
    77  
    78  		// Embedded scalars could still have arcs.
    79  		if final {
    80  			return true
    81  		}
    82  
    83  	default:
    84  		panic(fmt.Sprintf("unexpected type %T", v))
    85  	}
    86  
    87  	xClosed := x.IsClosedStruct() && !s.IgnoreClosedness
    88  	// TODO: this should not close for taking defaults. Do a more principled
    89  	// makeover of this package before making it public, though.
    90  	yClosed := s.Final || s.Defaults ||
    91  		(y.IsClosedStruct() && !s.IgnoreClosedness)
    92  
    93  	if xClosed && !yClosed && !final {
    94  		return false
    95  	}
    96  
    97  	types := x.OptionalTypes()
    98  	if !final && !s.IgnoreOptional && types&(adt.HasPattern|adt.HasAdditional) != 0 {
    99  		// TODO: there are many cases where pattern constraints can be checked.
   100  		s.inexact = true
   101  		return false
   102  	}
   103  
   104  	// All arcs in x must exist in y and its values must subsume.
   105  	xFeatures := export.VertexFeatures(s.ctx, x)
   106  	for _, f := range xFeatures {
   107  		if s.Final && !f.IsRegular() {
   108  			continue
   109  		}
   110  
   111  		a := x.Lookup(f)
   112  		aOpt := false
   113  		if a == nil {
   114  			// x.f is optional
   115  			if s.IgnoreOptional {
   116  				continue
   117  			}
   118  
   119  			a = &adt.Vertex{Label: f}
   120  			x.MatchAndInsert(ctx, a)
   121  			a.Finalize(ctx)
   122  
   123  			// If field a is optional and has value top, neither the
   124  			// omission of the field nor the field defined with any value
   125  			// may cause unification to fail.
   126  			if a.Kind() == adt.TopKind {
   127  				continue
   128  			}
   129  
   130  			aOpt = true
   131  		} else if a.IsConstraint() {
   132  			if s.IgnoreOptional {
   133  				continue
   134  			}
   135  			// If field a is optional and has value top, neither the
   136  			// omission of the field nor the field defined with any value
   137  			// may cause unification to fail.
   138  			if a.Kind() == adt.TopKind {
   139  				continue
   140  			}
   141  			aOpt = true
   142  		}
   143  
   144  		b := y.Lookup(f)
   145  		if b == nil {
   146  			// y.f is optional
   147  			if !aOpt {
   148  				s.errf("required field is optional in subsumed value: %v", f)
   149  				return false
   150  			}
   151  
   152  			// If f is undefined for y and if y is closed, the field is
   153  			// implicitly defined as _|_ and thus subsumed. Technically, this is
   154  			// even true if a is not optional, but in that case it means that y
   155  			// is invalid, so return false regardless
   156  			if !y.Accept(ctx, f) || y.IsData() || s.Final {
   157  				continue
   158  			}
   159  
   160  			b = &adt.Vertex{Label: f}
   161  			y.MatchAndInsert(ctx, b)
   162  			b.Finalize(ctx)
   163  		}
   164  
   165  		if s.values(a, b) {
   166  			continue
   167  		}
   168  
   169  		s.missing = f
   170  		s.gt = a
   171  		s.lt = y
   172  
   173  		s.errf("field %v not present in %v", f, y)
   174  		return false
   175  	}
   176  
   177  	if xClosed && !yClosed && !s.Final {
   178  		s.errf("closed struct does not subsume open struct")
   179  		return false
   180  	}
   181  
   182  	yFeatures := export.VertexFeatures(s.ctx, y)
   183  outer:
   184  	for _, f := range yFeatures {
   185  		if s.Final && !f.IsRegular() {
   186  			continue
   187  		}
   188  
   189  		for _, g := range xFeatures {
   190  			if g == f {
   191  				// already validated
   192  				continue outer
   193  			}
   194  		}
   195  
   196  		b := y.Lookup(f)
   197  		if b == nil {
   198  			if s.IgnoreOptional || s.Final {
   199  				continue
   200  			}
   201  
   202  			b = &adt.Vertex{Label: f}
   203  			y.MatchAndInsert(ctx, b)
   204  		} else if b.IsConstraint() {
   205  			if s.IgnoreOptional || s.Final {
   206  				continue
   207  			}
   208  		}
   209  
   210  		if !x.Accept(ctx, f) {
   211  			if s.Profile.IgnoreClosedness {
   212  				continue
   213  			}
   214  			s.errf("field not allowed in closed struct: %v", f)
   215  			return false
   216  		}
   217  
   218  		a := &adt.Vertex{Label: f}
   219  		x.MatchAndInsert(ctx, a)
   220  		if len(a.Conjuncts) == 0 {
   221  			// It is accepted and has no further constraints, so all good.
   222  			continue
   223  		}
   224  
   225  		a.Finalize(ctx)
   226  		b.Finalize(ctx)
   227  
   228  		if !s.vertices(a, b) {
   229  			return false
   230  		}
   231  	}
   232  
   233  	return true
   234  }
   235  
   236  func (s *subsumer) listVertices(x, y *adt.Vertex) bool {
   237  	ctx := s.ctx
   238  
   239  	if !y.IsData() && x.IsClosedList() && !y.IsClosedList() {
   240  		return false
   241  	}
   242  
   243  	xElems := x.Elems()
   244  	yElems := y.Elems()
   245  
   246  	switch {
   247  	case len(xElems) == len(yElems):
   248  	case len(xElems) > len(yElems):
   249  		return false
   250  	case x.IsClosedList():
   251  		return false
   252  	default:
   253  		a := &adt.Vertex{Label: adt.AnyIndex}
   254  		x.MatchAndInsert(ctx, a)
   255  		a.Finalize(ctx)
   256  
   257  		// x must be open
   258  		for _, b := range yElems[len(xElems):] {
   259  			if !s.vertices(a, b) {
   260  				return false
   261  			}
   262  		}
   263  
   264  		if !y.IsClosedList() {
   265  			b := &adt.Vertex{Label: adt.AnyIndex}
   266  			y.MatchAndInsert(ctx, b)
   267  			b.Finalize(ctx)
   268  		}
   269  	}
   270  
   271  	for i, a := range xElems {
   272  		if !s.vertices(a, yElems[i]) {
   273  			return false
   274  		}
   275  	}
   276  
   277  	return true
   278  }
   279
View as plain text