Source file src/github.com/bazelbuild/bazel-gazelle/rule/merge.go

Documentation: github.com/bazelbuild/bazel-gazelle/rule

     1  /* Copyright 2018 The Bazel Authors. All rights reserved.
     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  
    16  package rule
    17  
    18  import (
    19  	"errors"
    20  	"fmt"
    21  	"log"
    22  	"sort"
    23  
    24  	bzl "github.com/bazelbuild/buildtools/build"
    25  )
    26  
    27  // MergeRules copies information from src into dst, usually discarding
    28  // information in dst when they have the same attributes.
    29  //
    30  // If dst is marked with a "# keep" comment, either above the rule or as
    31  // a suffix, nothing will be changed.
    32  //
    33  // If src has an attribute that is not in dst, it will be copied into dst.
    34  //
    35  // If src and dst have the same attribute and the attribute is mergeable and the
    36  // attribute in dst is not marked with a "# keep" comment, values in the dst
    37  // attribute not marked with a "# keep" comment will be dropped, and values from
    38  // src will be copied in.
    39  //
    40  // If dst has an attribute not in src, and the attribute is mergeable and not
    41  // marked with a "# keep" comment, values in the attribute not marked with
    42  // a "# keep" comment will be dropped. If the attribute is empty afterward,
    43  // it will be deleted.
    44  func MergeRules(src, dst *Rule, mergeable map[string]bool, filename string) {
    45  	if dst.ShouldKeep() {
    46  		return
    47  	}
    48  
    49  	// Process attributes that are in dst but not in src.
    50  	for key, dstAttr := range dst.attrs {
    51  		if _, ok := src.attrs[key]; ok || !mergeable[key] || ShouldKeep(dstAttr.expr) {
    52  			continue
    53  		}
    54  		if mergedValue, err := mergeAttrValues(nil, &dstAttr); err != nil {
    55  			start, end := dstAttr.expr.RHS.Span()
    56  			log.Printf("%s:%d.%d-%d.%d: could not merge expression", filename, start.Line, start.LineRune, end.Line, end.LineRune)
    57  		} else if mergedValue == nil {
    58  			dst.DelAttr(key)
    59  		} else {
    60  			dst.SetAttr(key, mergedValue)
    61  		}
    62  	}
    63  
    64  	// Merge attributes from src into dst.
    65  	for key, srcAttr := range src.attrs {
    66  		if dstAttr, ok := dst.attrs[key]; !ok {
    67  			dst.SetAttr(key, srcAttr.expr.RHS)
    68  		} else if mergeable[key] && !ShouldKeep(dstAttr.expr) {
    69  			if mergedValue, err := mergeAttrValues(&srcAttr, &dstAttr); err != nil {
    70  				start, end := dstAttr.expr.RHS.Span()
    71  				log.Printf("%s:%d.%d-%d.%d: could not merge expression", filename, start.Line, start.LineRune, end.Line, end.LineRune)
    72  			} else if mergedValue == nil {
    73  				dst.DelAttr(key)
    74  			} else {
    75  				dst.SetAttr(key, mergedValue)
    76  			}
    77  		}
    78  	}
    79  
    80  	dst.private = src.private
    81  }
    82  
    83  // mergeAttrValues combines information from src and dst and returns a merged
    84  // expression. dst may be modified during this process. The returned expression
    85  // may be different from dst when a structural change is needed.
    86  //
    87  // The following kinds of expressions are recognized.
    88  //
    89  //   * nil
    90  //   * strings (can only be merged with strings)
    91  //   * lists of strings
    92  //   * a call to select with a dict argument. The dict keys must be strings,
    93  //     and the values must be lists of strings.
    94  //   * a list of strings combined with a select call using +. The list must
    95  //     be the left operand.
    96  //   * an attr value that implements the Merger interface.
    97  //
    98  // An error is returned if the expressions can't be merged, for example
    99  // because they are not in one of the above formats.
   100  func mergeAttrValues(srcAttr, dstAttr *attrValue) (bzl.Expr, error) {
   101  	if ShouldKeep(dstAttr.expr.RHS) {
   102  		return nil, nil
   103  	}
   104  	dst := dstAttr.expr.RHS
   105  	if srcAttr == nil && (dst == nil || isScalar(dst)) {
   106  		return nil, nil
   107  	}
   108  	if srcAttr != nil && isScalar(srcAttr.expr.RHS) {
   109  		return srcAttr.expr.RHS, nil
   110  	}
   111  
   112  	if _, ok := dstAttr.val.(Merger); srcAttr == nil && ok {
   113  		return nil, nil
   114  	}
   115  
   116  	if srcAttr != nil {
   117  		if srcMerger, ok := srcAttr.val.(Merger); ok {
   118  			return srcMerger.Merge(dst), nil
   119  		}
   120  	}
   121  	var srcExprs platformStringsExprs
   122  	var err error
   123  	if srcAttr != nil {
   124  		srcExprs, err = extractPlatformStringsExprs(srcAttr.expr.RHS)
   125  		if err != nil {
   126  			return nil, err
   127  		}
   128  	}
   129  
   130  	dstExprs, err := extractPlatformStringsExprs(dst)
   131  	if err != nil {
   132  		return nil, err
   133  	}
   134  	mergedExprs, err := mergePlatformStringsExprs(srcExprs, dstExprs)
   135  	if err != nil {
   136  		return nil, err
   137  	}
   138  	return makePlatformStringsExpr(mergedExprs), nil
   139  }
   140  
   141  func mergePlatformStringsExprs(src, dst platformStringsExprs) (platformStringsExprs, error) {
   142  	var ps platformStringsExprs
   143  	var err error
   144  	ps.generic = MergeList(src.generic, dst.generic)
   145  	if ps.os, err = MergeDict(src.os, dst.os); err != nil {
   146  		return platformStringsExprs{}, err
   147  	}
   148  	if ps.arch, err = MergeDict(src.arch, dst.arch); err != nil {
   149  		return platformStringsExprs{}, err
   150  	}
   151  	if ps.platform, err = MergeDict(src.platform, dst.platform); err != nil {
   152  		return platformStringsExprs{}, err
   153  	}
   154  	return ps, nil
   155  }
   156  
   157  // MergeList merges two bzl.ListExpr of strings. The lists are merged in the
   158  // following way:
   159  //
   160  //   - If a string appears in both lists, it appears in the result.
   161  //   - If a string appears in only src list, it appears in the result.
   162  //   - If a string appears in only dst list, it is dropped from the result.
   163  //   - If a string appears in neither list, it is dropped from the result.
   164  //
   165  // The result is nil if both lists are nil or empty.
   166  //
   167  // If the result is non-nil, it will have ForceMultiLine set if either of the
   168  // input lists has ForceMultiLine set or if any of the strings in the result
   169  // have a "# keep" comment.
   170  func MergeList(srcExpr, dstExpr bzl.Expr) *bzl.ListExpr {
   171  	src, isSrcLis := srcExpr.(*bzl.ListExpr)
   172  	dst, isDstLis := dstExpr.(*bzl.ListExpr)
   173  	if !isSrcLis && !isDstLis {
   174  		return nil
   175  	}
   176  	if dst == nil {
   177  		return src
   178  	}
   179  	if src == nil {
   180  		src = &bzl.ListExpr{List: []bzl.Expr{}}
   181  	}
   182  
   183  	// Build a list of strings from the src list and keep matching strings
   184  	// in the dst list. This preserves comments. Also keep anything with
   185  	// a "# keep" comment, whether or not it's in the src list.
   186  	srcSet := make(map[string]bool)
   187  	for _, v := range src.List {
   188  		if s := stringValue(v); s != "" {
   189  			srcSet[s] = true
   190  		}
   191  	}
   192  
   193  	var merged []bzl.Expr
   194  	kept := make(map[string]bool)
   195  	keepComment := false
   196  	for _, v := range dst.List {
   197  		s := stringValue(v)
   198  		if keep := ShouldKeep(v); keep || srcSet[s] {
   199  			keepComment = keepComment || keep
   200  			merged = append(merged, v)
   201  			if s != "" {
   202  				kept[s] = true
   203  			}
   204  		}
   205  	}
   206  
   207  	// Add anything in the src list that wasn't kept.
   208  	for _, v := range src.List {
   209  		if s := stringValue(v); kept[s] {
   210  			continue
   211  		}
   212  		merged = append(merged, v)
   213  	}
   214  
   215  	if len(merged) == 0 {
   216  		return nil
   217  	}
   218  	return &bzl.ListExpr{
   219  		List:           merged,
   220  		ForceMultiLine: src.ForceMultiLine || dst.ForceMultiLine || keepComment,
   221  	}
   222  }
   223  
   224  // MergeDict merges two bzl.DictExpr, src and dst, where the keys are strings
   225  // and the values are lists of strings.
   226  //
   227  // If both src and dst are non-nil, the keys in src are merged into dst. If both
   228  // src and dst have the same key, the values are merged using MergeList.
   229  // If the same key is present in both src and dst, and the values are not compatible,
   230  // an error is returned.
   231  func MergeDict(srcExpr, dstExpr bzl.Expr) (*bzl.DictExpr, error) {
   232  	src, isSrcDict := srcExpr.(*bzl.DictExpr)
   233  	dst, isDstDict := dstExpr.(*bzl.DictExpr)
   234  	if !isSrcDict && !isDstDict {
   235  		return nil, fmt.Errorf("expected dict, got %s and %s", srcExpr, dstExpr)
   236  	}
   237  	if dst == nil {
   238  		return src, nil
   239  	}
   240  	if src == nil {
   241  		src = &bzl.DictExpr{List: []*bzl.KeyValueExpr{}}
   242  	}
   243  
   244  	var entries []*dictEntry
   245  	entryMap := make(map[string]*dictEntry)
   246  
   247  	for _, kv := range dst.List {
   248  		k, v, err := dictEntryKeyValue(kv)
   249  		if err != nil {
   250  			return nil, err
   251  		}
   252  		if _, ok := entryMap[k]; ok {
   253  			return nil, fmt.Errorf("dst dict contains more than one case named %q", k)
   254  		}
   255  		e := &dictEntry{key: k, dstValue: v}
   256  		entries = append(entries, e)
   257  		entryMap[k] = e
   258  	}
   259  
   260  	for _, kv := range src.List {
   261  		k, v, err := dictEntryKeyValue(kv)
   262  		if err != nil {
   263  			return nil, err
   264  		}
   265  		e, ok := entryMap[k]
   266  		if !ok {
   267  			e = &dictEntry{key: k}
   268  			entries = append(entries, e)
   269  			entryMap[k] = e
   270  		}
   271  		e.srcValue = v
   272  	}
   273  
   274  	keys := make([]string, 0, len(entries))
   275  	haveDefault := false
   276  	for _, e := range entries {
   277  		e.mergedValue = MergeList(e.srcValue, e.dstValue)
   278  		if e.key == "//conditions:default" {
   279  			// Keep the default case, even if it's empty.
   280  			haveDefault = true
   281  			if e.mergedValue == nil {
   282  				e.mergedValue = &bzl.ListExpr{}
   283  			}
   284  		} else if e.mergedValue != nil {
   285  			keys = append(keys, e.key)
   286  		}
   287  	}
   288  	if len(keys) == 0 && (!haveDefault || len(entryMap["//conditions:default"].mergedValue.List) == 0) {
   289  		return nil, nil
   290  	}
   291  	sort.Strings(keys)
   292  	// Always put the default case last.
   293  	if haveDefault {
   294  		keys = append(keys, "//conditions:default")
   295  	}
   296  
   297  	mergedEntries := make([]*bzl.KeyValueExpr, len(keys))
   298  	for i, k := range keys {
   299  		e := entryMap[k]
   300  		mergedEntries[i] = &bzl.KeyValueExpr{
   301  			Key:   &bzl.StringExpr{Value: e.key},
   302  			Value: e.mergedValue,
   303  		}
   304  	}
   305  
   306  	return &bzl.DictExpr{List: mergedEntries, ForceMultiLine: true}, nil
   307  }
   308  
   309  type dictEntry struct {
   310  	key                             string
   311  	dstValue, srcValue, mergedValue *bzl.ListExpr
   312  }
   313  
   314  // SquashRules copies information from src into dst without discarding
   315  // information in dst. SquashRules detects duplicate elements in lists and
   316  // dictionaries, but it doesn't sort elements after squashing. If squashing
   317  // fails because the expression is not understood, an error is returned,
   318  // and neither rule is modified.
   319  func SquashRules(src, dst *Rule, filename string) error {
   320  	if dst.ShouldKeep() {
   321  		return nil
   322  	}
   323  
   324  	for key, srcAttr := range src.attrs {
   325  		srcValue := srcAttr.expr.RHS
   326  		if dstAttr, ok := dst.attrs[key]; !ok {
   327  			dst.SetAttr(key, srcValue)
   328  		} else if !ShouldKeep(dstAttr.expr) {
   329  			dstValue := dstAttr.expr.RHS
   330  			if squashedValue, err := squashExprs(srcValue, dstValue); err != nil {
   331  				start, end := dstValue.Span()
   332  				return fmt.Errorf("%s:%d.%d-%d.%d: could not squash expression", filename, start.Line, start.LineRune, end.Line, end.LineRune)
   333  			} else {
   334  				dst.SetAttr(key, squashedValue)
   335  			}
   336  		}
   337  	}
   338  	dst.expr.Comment().Before = append(dst.expr.Comment().Before, src.expr.Comment().Before...)
   339  	dst.expr.Comment().Suffix = append(dst.expr.Comment().Suffix, src.expr.Comment().Suffix...)
   340  	dst.expr.Comment().After = append(dst.expr.Comment().After, src.expr.Comment().After...)
   341  	return nil
   342  }
   343  
   344  func squashExprs(src, dst bzl.Expr) (bzl.Expr, error) {
   345  	if ShouldKeep(dst) {
   346  		return dst, nil
   347  	}
   348  	if isScalar(dst) {
   349  		// may lose src, but they should always be the same.
   350  		return dst, nil
   351  	}
   352  	srcExprs, err := extractPlatformStringsExprs(src)
   353  	if err != nil {
   354  		return nil, err
   355  	}
   356  	dstExprs, err := extractPlatformStringsExprs(dst)
   357  	if err != nil {
   358  		return nil, err
   359  	}
   360  	squashedExprs, err := squashPlatformStringsExprs(srcExprs, dstExprs)
   361  	if err != nil {
   362  		return nil, err
   363  	}
   364  	return makePlatformStringsExpr(squashedExprs), nil
   365  }
   366  
   367  func squashPlatformStringsExprs(x, y platformStringsExprs) (platformStringsExprs, error) {
   368  	var ps platformStringsExprs
   369  	var err error
   370  	if ps.generic, err = squashList(x.generic, y.generic); err != nil {
   371  		return platformStringsExprs{}, err
   372  	}
   373  	if ps.os, err = squashDict(x.os, y.os); err != nil {
   374  		return platformStringsExprs{}, err
   375  	}
   376  	if ps.arch, err = squashDict(x.arch, y.arch); err != nil {
   377  		return platformStringsExprs{}, err
   378  	}
   379  	if ps.platform, err = squashDict(x.platform, y.platform); err != nil {
   380  		return platformStringsExprs{}, err
   381  	}
   382  	return ps, nil
   383  }
   384  
   385  func squashList(x, y *bzl.ListExpr) (*bzl.ListExpr, error) {
   386  	if x == nil {
   387  		return y, nil
   388  	}
   389  	if y == nil {
   390  		return x, nil
   391  	}
   392  
   393  	ls := makeListSquasher()
   394  	for _, e := range x.List {
   395  		s, ok := e.(*bzl.StringExpr)
   396  		if !ok {
   397  			return nil, errors.New("could not squash non-string")
   398  		}
   399  		ls.add(s)
   400  	}
   401  	for _, e := range y.List {
   402  		s, ok := e.(*bzl.StringExpr)
   403  		if !ok {
   404  			return nil, errors.New("could not squash non-string")
   405  		}
   406  		ls.add(s)
   407  	}
   408  	squashed := ls.list()
   409  	squashed.Comments.Before = append(x.Comments.Before, y.Comments.Before...)
   410  	squashed.Comments.Suffix = append(x.Comments.Suffix, y.Comments.Suffix...)
   411  	squashed.Comments.After = append(x.Comments.After, y.Comments.After...)
   412  	return squashed, nil
   413  }
   414  
   415  func squashDict(x, y *bzl.DictExpr) (*bzl.DictExpr, error) {
   416  	if x == nil {
   417  		return y, nil
   418  	}
   419  	if y == nil {
   420  		return x, nil
   421  	}
   422  
   423  	cases := make(map[string]*bzl.KeyValueExpr)
   424  	addCase := func(e bzl.Expr) error {
   425  		kv := e.(*bzl.KeyValueExpr)
   426  		key, ok := kv.Key.(*bzl.StringExpr)
   427  		if !ok {
   428  			return errors.New("could not squash non-string dict key")
   429  		}
   430  		if _, ok := kv.Value.(*bzl.ListExpr); !ok {
   431  			return errors.New("could not squash non-list dict value")
   432  		}
   433  		if c, ok := cases[key.Value]; ok {
   434  			if sq, err := squashList(kv.Value.(*bzl.ListExpr), c.Value.(*bzl.ListExpr)); err != nil {
   435  				return err
   436  			} else {
   437  				c.Value = sq
   438  			}
   439  		} else {
   440  			kvCopy := *kv
   441  			cases[key.Value] = &kvCopy
   442  		}
   443  		return nil
   444  	}
   445  
   446  	for _, e := range x.List {
   447  		if err := addCase(e); err != nil {
   448  			return nil, err
   449  		}
   450  	}
   451  	for _, e := range y.List {
   452  		if err := addCase(e); err != nil {
   453  			return nil, err
   454  		}
   455  	}
   456  
   457  	keys := make([]string, 0, len(cases))
   458  	haveDefault := false
   459  	for k := range cases {
   460  		if k == "//conditions:default" {
   461  			haveDefault = true
   462  			continue
   463  		}
   464  		keys = append(keys, k)
   465  	}
   466  	sort.Strings(keys)
   467  	if haveDefault {
   468  		keys = append(keys, "//conditions:default") // must be last
   469  	}
   470  
   471  	squashed := *x
   472  	squashed.Comments.Before = append(x.Comments.Before, y.Comments.Before...)
   473  	squashed.Comments.Suffix = append(x.Comments.Suffix, y.Comments.Suffix...)
   474  	squashed.Comments.After = append(x.Comments.After, y.Comments.After...)
   475  	squashed.List = make([]*bzl.KeyValueExpr, 0, len(cases))
   476  	for _, k := range keys {
   477  		squashed.List = append(squashed.List, cases[k])
   478  	}
   479  	return &squashed, nil
   480  }
   481  
   482  // listSquasher builds a sorted, deduplicated list of string expressions. If
   483  // a string expression is added multiple times, comments are consolidated.
   484  // The original expressions are not modified.
   485  type listSquasher struct {
   486  	unique       map[string]*bzl.StringExpr
   487  	seenComments map[elemComment]bool
   488  }
   489  
   490  type elemComment struct {
   491  	elem, com string
   492  }
   493  
   494  func makeListSquasher() listSquasher {
   495  	return listSquasher{
   496  		unique:       make(map[string]*bzl.StringExpr),
   497  		seenComments: make(map[elemComment]bool),
   498  	}
   499  }
   500  
   501  func (ls *listSquasher) add(s *bzl.StringExpr) {
   502  	sCopy, ok := ls.unique[s.Value]
   503  	if !ok {
   504  		// Make a copy of s. We may modify it when we consolidate comments from
   505  		// duplicate strings. We don't want to modify the original in case this
   506  		// function fails (due to a later failed pattern match).
   507  		sCopy = new(bzl.StringExpr)
   508  		*sCopy = *s
   509  		sCopy.Comments.Before = make([]bzl.Comment, 0, len(s.Comments.Before))
   510  		sCopy.Comments.Suffix = make([]bzl.Comment, 0, len(s.Comments.Suffix))
   511  		ls.unique[s.Value] = sCopy
   512  	}
   513  	for _, c := range s.Comment().Before {
   514  		if key := (elemComment{s.Value, c.Token}); !ls.seenComments[key] {
   515  			sCopy.Comments.Before = append(sCopy.Comments.Before, c)
   516  			ls.seenComments[key] = true
   517  		}
   518  	}
   519  	for _, c := range s.Comment().Suffix {
   520  		if key := (elemComment{s.Value, c.Token}); !ls.seenComments[key] {
   521  			sCopy.Comments.Suffix = append(sCopy.Comments.Suffix, c)
   522  			ls.seenComments[key] = true
   523  		}
   524  	}
   525  }
   526  
   527  func (ls *listSquasher) list() *bzl.ListExpr {
   528  	sortedExprs := make([]bzl.Expr, 0, len(ls.unique))
   529  	for _, e := range ls.unique {
   530  		sortedExprs = append(sortedExprs, e)
   531  	}
   532  	sort.Slice(sortedExprs, func(i, j int) bool {
   533  		return sortedExprs[i].(*bzl.StringExpr).Value < sortedExprs[j].(*bzl.StringExpr).Value
   534  	})
   535  	return &bzl.ListExpr{List: sortedExprs}
   536  }
   537  

View as plain text