1// Copyright 2019 Google Inc. 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
15package proptools
16
17import (
18	"fmt"
19	"reflect"
20	"strconv"
21)
22
23type FilterFieldPredicate func(field reflect.StructField, string string) (bool, reflect.StructField)
24
25type cantFitPanic struct {
26	field reflect.StructField
27	size  int
28}
29
30func (x cantFitPanic) Error() string {
31	return fmt.Sprintf("Can't fit field %s %s %s size %d into %d",
32		x.field.Name, x.field.Type.String(), strconv.Quote(string(x.field.Tag)),
33		fieldToTypeNameSize(x.field, true)+2, x.size)
34}
35
36// All runtime created structs will have a name that starts with "struct {" and ends with "}"
37const emptyStructTypeNameSize = len("struct {}")
38
39func filterPropertyStructFields(fields []reflect.StructField, prefix string, maxTypeNameSize int,
40	predicate FilterFieldPredicate) (filteredFieldsShards [][]reflect.StructField, filtered bool) {
41
42	structNameSize := emptyStructTypeNameSize
43
44	var filteredFields []reflect.StructField
45
46	appendAndShardIfNameFull := func(field reflect.StructField) {
47		fieldTypeNameSize := fieldToTypeNameSize(field, true)
48		// Every field will have a space before it and either a semicolon or space after it.
49		fieldTypeNameSize += 2
50
51		if maxTypeNameSize > 0 && structNameSize+fieldTypeNameSize > maxTypeNameSize {
52			if len(filteredFields) == 0 {
53				if isStruct(field.Type) || isStructPtr(field.Type) {
54					// An error fitting the nested struct should have been caught when recursing
55					// into the nested struct.
56					panic(fmt.Errorf("Shouldn't happen: can't fit nested struct %q (%d) into %d",
57						field.Type.String(), len(field.Type.String()), maxTypeNameSize-structNameSize))
58				}
59				panic(cantFitPanic{field, maxTypeNameSize - structNameSize})
60
61			}
62			filteredFieldsShards = append(filteredFieldsShards, filteredFields)
63			filteredFields = nil
64			structNameSize = emptyStructTypeNameSize
65		}
66
67		filteredFields = append(filteredFields, field)
68		structNameSize += fieldTypeNameSize
69	}
70
71	for _, field := range fields {
72		var keep bool
73		if keep, field = predicate(field, prefix); !keep {
74			filtered = true
75			continue
76		}
77
78		subPrefix := field.Name
79		if prefix != "" {
80			subPrefix = prefix + "." + subPrefix
81		}
82
83		ptrToStruct := false
84		if isStructPtr(field.Type) {
85			ptrToStruct = true
86		}
87
88		// Recurse into structs
89		if ptrToStruct || isStruct(field.Type) {
90			subMaxTypeNameSize := maxTypeNameSize
91			if maxTypeNameSize > 0 {
92				// In the worst case where only this nested struct will fit in the outer struct, the
93				// outer struct will contribute struct{}, the name and tag of the field that contains
94				// the nested struct, and one space before and after the field.
95				subMaxTypeNameSize -= emptyStructTypeNameSize + fieldToTypeNameSize(field, false) + 2
96			}
97			typ := field.Type
98			if ptrToStruct {
99				subMaxTypeNameSize -= len("*")
100				typ = typ.Elem()
101			}
102			nestedTypes, subFiltered := filterPropertyStruct(typ, subPrefix, subMaxTypeNameSize, predicate)
103			filtered = filtered || subFiltered
104			if nestedTypes == nil {
105				continue
106			}
107
108			for _, nestedType := range nestedTypes {
109				if ptrToStruct {
110					nestedType = reflect.PtrTo(nestedType)
111				}
112				field.Type = nestedType
113				appendAndShardIfNameFull(field)
114			}
115		} else {
116			appendAndShardIfNameFull(field)
117		}
118	}
119
120	if len(filteredFields) > 0 {
121		filteredFieldsShards = append(filteredFieldsShards, filteredFields)
122	}
123
124	return filteredFieldsShards, filtered
125}
126
127func fieldToTypeNameSize(field reflect.StructField, withType bool) int {
128	nameSize := len(field.Name)
129	nameSize += len(" ")
130	if withType {
131		nameSize += len(field.Type.String())
132	}
133	if field.Tag != "" {
134		nameSize += len(" ")
135		nameSize += len(strconv.Quote(string(field.Tag)))
136	}
137	return nameSize
138}
139
140// FilterPropertyStruct takes a reflect.Type that is either a struct or a pointer to a struct, and returns a
141// reflect.Type that only contains the fields in the original type for which predicate returns true, and a bool
142// that is true if the new struct type has fewer fields than the original type.  If there are no fields in the
143// original type for which predicate returns true it returns nil and true.
144func FilterPropertyStruct(prop reflect.Type, predicate FilterFieldPredicate) (filteredProp reflect.Type, filtered bool) {
145	filteredFieldsShards, filtered := filterPropertyStruct(prop, "", -1, predicate)
146	switch len(filteredFieldsShards) {
147	case 0:
148		return nil, filtered
149	case 1:
150		return filteredFieldsShards[0], filtered
151	default:
152		panic("filterPropertyStruct should only return 1 struct if maxNameSize < 0")
153	}
154}
155
156func filterPropertyStruct(prop reflect.Type, prefix string, maxNameSize int,
157	predicate FilterFieldPredicate) (filteredProp []reflect.Type, filtered bool) {
158
159	var fields []reflect.StructField
160
161	ptr := prop.Kind() == reflect.Ptr
162	if ptr {
163		prop = prop.Elem()
164	}
165
166	for i := 0; i < prop.NumField(); i++ {
167		fields = append(fields, prop.Field(i))
168	}
169
170	filteredFieldsShards, filtered := filterPropertyStructFields(fields, prefix, maxNameSize, predicate)
171
172	if len(filteredFieldsShards) == 0 {
173		return nil, true
174	}
175
176	// If the predicate selected all fields in the structure then it is generally better to reuse the
177	// original type as it avoids the footprint of creating another type. Also, if the original type
178	// is a named type then it will reduce the size of any structs the caller may create that include
179	// fields of this type. However, the original type should only be reused if it does not exceed
180	// maxNameSize. That is, of course, more likely for an anonymous type than a named one but this
181	// treats them the same.
182	if !filtered && (maxNameSize < 0 || len(prop.String()) < maxNameSize) {
183		if ptr {
184			return []reflect.Type{reflect.PtrTo(prop)}, false
185		}
186		return []reflect.Type{prop}, false
187	}
188
189	var ret []reflect.Type
190	for _, filteredFields := range filteredFieldsShards {
191		p := reflect.StructOf(filteredFields)
192		if ptr {
193			p = reflect.PtrTo(p)
194		}
195		ret = append(ret, p)
196	}
197
198	return ret, true
199}
200
201// FilterPropertyStructSharded takes a reflect.Type that is either a sturct or a pointer to a struct, and returns a list
202// of reflect.Type that only contains the fields in the original type for which predicate returns true, and a bool that
203// is true if the new struct type has fewer fields than the original type.  If there are no fields in the original type
204// for which predicate returns true it returns nil and true.  Each returned struct type will have a maximum of 10 top
205// level fields in it to attempt to avoid hitting the 65535 byte type name length limit in reflect.StructOf
206// (reflect.nameFrom: name too long), although the limit can still be reached with a single struct field with many
207// fields in it.
208func FilterPropertyStructSharded(prop reflect.Type, maxTypeNameSize int, predicate FilterFieldPredicate) (filteredProp []reflect.Type, filtered bool) {
209	return filterPropertyStruct(prop, "", maxTypeNameSize, predicate)
210}
211