1// Copyright 2021 The Tint 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 15package gen 16 17import ( 18 "fmt" 19 20 "dawn.googlesource.com/tint/tools/src/cmd/intrinsic-gen/sem" 21 "dawn.googlesource.com/tint/tools/src/list" 22 "dawn.googlesource.com/tint/tools/src/lut" 23) 24 25// IntrinsicTable holds data specific to the intrinsic_table.inl.tmpl template 26type IntrinsicTable struct { 27 // The semantic info 28 Sem *sem.Sem 29 30 // TMatchers are all the sem.OpenType, sem.Type and sem.TypeMatchers. 31 // These are all implemented by classes deriving from tint::TypeMatcher 32 TMatchers []sem.Named 33 TMatcherIndex map[sem.Named]int // [object -> index] in TMatcher 34 35 // NMatchers are all the sem.OpenNumber and sem.EnumMatchers. 36 // These are all implemented by classes deriving from tint::NumberMatcher 37 NMatchers []sem.Named 38 NMatcherIndex map[sem.Named]int // [object -> index] in NMatchers 39 40 MatcherIndices []int // kMatcherIndices table content 41 OpenTypes []OpenType // kOpenTypes table content 42 OpenNumbers []OpenNumber // kOpenNumbers table content 43 Parameters []Parameter // kParameters table content 44 Overloads []Overload // kOverloads table content 45 Functions []Function // kIntrinsics table content 46} 47 48// OpenType is used to create the C++ OpenTypeInfo structure 49type OpenType struct { 50 // Name of the open type (e.g. 'T') 51 Name string 52 // Optional type matcher constraint. 53 // Either an index in Matchers::type, or -1 54 MatcherIndex int 55} 56 57// OpenNumber is used to create the C++ OpenNumberInfo structure 58type OpenNumber struct { 59 // Name of the open number (e.g. 'N') 60 Name string 61 // Optional type matcher constraint. 62 // Either an index in Matchers::type, or -1 63 MatcherIndex int 64} 65 66// Parameter is used to create the C++ ParameterInfo structure 67type Parameter struct { 68 // The parameter usage (parameter name) 69 Usage string 70 71 // Index into IntrinsicTable.MatcherIndices, beginning the list of matchers 72 // required to match the parameter type. The matcher indices index 73 // into IntrinsicTable::TMatchers and / or IntrinsicTable::NMatchers. 74 // These indices are consumed by the matchers themselves. 75 // The first index is always a TypeMatcher. 76 MatcherIndicesOffset *int 77} 78 79// Overload is used to create the C++ OverloadInfo structure 80type Overload struct { 81 // Total number of parameters for the overload 82 NumParameters int 83 // Total number of open types for the overload 84 NumOpenTypes int 85 // Total number of open numbers for the overload 86 NumOpenNumbers int 87 // Index to the first open type in IntrinsicTable.OpenTypes 88 OpenTypesOffset *int 89 // Index to the first open number in IntrinsicTable.OpenNumbers 90 OpenNumbersOffset *int 91 // Index to the first parameter in IntrinsicTable.Parameters 92 ParametersOffset *int 93 // Index into IntrinsicTable.MatcherIndices, beginning the list of matchers 94 // required to match the return type. The matcher indices index 95 // into IntrinsicTable::TMatchers and / or IntrinsicTable::NMatchers. 96 // These indices are consumed by the matchers themselves. 97 // The first index is always a TypeMatcher. 98 ReturnMatcherIndicesOffset *int 99 // StageUses describes the stages an overload can be used in 100 CanBeUsedInStage sem.StageUses 101 // True if the overload is marked as deprecated 102 IsDeprecated bool 103} 104 105// Function is used to create the C++ IntrinsicInfo structure 106type Function struct { 107 OverloadDescriptions []string 108 NumOverloads int 109 OverloadsOffset *int 110} 111 112// Helper for building the IntrinsicTable 113type intrinsicTableBuilder struct { 114 // The output of the builder 115 IntrinsicTable 116 117 // Lookup tables. 118 // These are packed (compressed) once all the entries have been added. 119 lut struct { 120 matcherIndices lut.LUT 121 openTypes lut.LUT 122 openNumbers lut.LUT 123 parameters lut.LUT 124 overloads lut.LUT 125 } 126} 127 128// Helper for building a single overload 129type overloadBuilder struct { 130 *intrinsicTableBuilder 131 // Maps TemplateParam to index in openTypes 132 openTypeIndex map[sem.TemplateParam]int 133 // Maps TemplateParam to index in openNumbers 134 openNumberIndex map[sem.TemplateParam]int 135 // Open types used by the overload 136 openTypes []OpenType 137 // Open numbers used by the overload 138 openNumbers []OpenNumber 139 // All parameters declared by the overload 140 parameters []Parameter 141 // Index into IntrinsicTable.MatcherIndices, beginning the list of matchers 142 // required to match the return type. The matcher indices index 143 // into IntrinsicTable::TMatchers and / or IntrinsicTable::NMatchers. 144 // These indices are consumed by the matchers themselves. 145 // The first index is always a TypeMatcher. 146 returnTypeMatcherIndicesOffset *int 147} 148 149// layoutMatchers assigns each of the TMatchers and NMatchers a unique index 150// in the C++ Matchers::type and Matchers::number arrays, respectively. 151func (b *intrinsicTableBuilder) layoutMatchers(s *sem.Sem) { 152 // First MaxOpenTypes of TMatchers are open types 153 b.TMatchers = make([]sem.Named, s.MaxOpenTypes) 154 for _, m := range s.Types { 155 b.TMatcherIndex[m] = len(b.TMatchers) 156 b.TMatchers = append(b.TMatchers, m) 157 } 158 for _, m := range s.TypeMatchers { 159 b.TMatcherIndex[m] = len(b.TMatchers) 160 b.TMatchers = append(b.TMatchers, m) 161 } 162 163 // First MaxOpenNumbers of NMatchers are open numbers 164 b.NMatchers = make([]sem.Named, s.MaxOpenNumbers) 165 for _, m := range s.EnumMatchers { 166 b.NMatcherIndex[m] = len(b.NMatchers) 167 b.NMatchers = append(b.NMatchers, m) 168 } 169} 170 171// buildOverload constructs an Overload for a sem.Overload 172func (b *intrinsicTableBuilder) buildOverload(o *sem.Overload) (Overload, error) { 173 ob := overloadBuilder{ 174 intrinsicTableBuilder: b, 175 openTypeIndex: map[sem.TemplateParam]int{}, 176 openNumberIndex: map[sem.TemplateParam]int{}, 177 } 178 179 if err := ob.buildOpenTypes(o); err != nil { 180 return Overload{}, err 181 } 182 if err := ob.buildOpenNumbers(o); err != nil { 183 return Overload{}, err 184 } 185 if err := ob.buildParameters(o); err != nil { 186 return Overload{}, err 187 } 188 if err := ob.buildReturnType(o); err != nil { 189 return Overload{}, err 190 } 191 192 return Overload{ 193 NumParameters: len(ob.parameters), 194 NumOpenTypes: len(ob.openTypes), 195 NumOpenNumbers: len(ob.openNumbers), 196 OpenTypesOffset: b.lut.openTypes.Add(ob.openTypes), 197 OpenNumbersOffset: b.lut.openNumbers.Add(ob.openNumbers), 198 ParametersOffset: b.lut.parameters.Add(ob.parameters), 199 ReturnMatcherIndicesOffset: ob.returnTypeMatcherIndicesOffset, 200 CanBeUsedInStage: o.CanBeUsedInStage, 201 IsDeprecated: o.IsDeprecated, 202 }, nil 203} 204 205// buildOpenTypes constructs the OpenTypes used by the overload, populating 206// b.openTypes 207func (b *overloadBuilder) buildOpenTypes(o *sem.Overload) error { 208 b.openTypes = make([]OpenType, len(o.OpenTypes)) 209 for i, t := range o.OpenTypes { 210 b.openTypeIndex[t] = i 211 matcherIndex := -1 212 if t.Type != nil { 213 var err error 214 matcherIndex, err = b.matcherIndex(t.Type) 215 if err != nil { 216 return err 217 } 218 } 219 b.openTypes[i] = OpenType{ 220 Name: t.Name, 221 MatcherIndex: matcherIndex, 222 } 223 } 224 return nil 225} 226 227// buildOpenNumbers constructs the OpenNumbers used by the overload, populating 228// b.openNumbers 229func (b *overloadBuilder) buildOpenNumbers(o *sem.Overload) error { 230 b.openNumbers = make([]OpenNumber, len(o.OpenNumbers)) 231 for i, t := range o.OpenNumbers { 232 b.openNumberIndex[t] = i 233 matcherIndex := -1 234 if e, ok := t.(*sem.TemplateEnumParam); ok && e.Matcher != nil { 235 var err error 236 matcherIndex, err = b.matcherIndex(e.Matcher) 237 if err != nil { 238 return err 239 } 240 } 241 b.openNumbers[i] = OpenNumber{ 242 Name: t.GetName(), 243 MatcherIndex: matcherIndex, 244 } 245 } 246 return nil 247} 248 249// buildParameters constructs the Parameters used by the overload, populating 250// b.parameters 251func (b *overloadBuilder) buildParameters(o *sem.Overload) error { 252 b.parameters = make([]Parameter, len(o.Parameters)) 253 for i, p := range o.Parameters { 254 indices, err := b.collectMatcherIndices(p.Type) 255 if err != nil { 256 return err 257 } 258 259 b.parameters[i] = Parameter{ 260 Usage: p.Name, 261 MatcherIndicesOffset: b.lut.matcherIndices.Add(indices), 262 } 263 } 264 return nil 265} 266 267// buildParameters calculates the matcher indices required to match the 268// overload's return type (if the overload has a return value), possibly 269// populating b.returnTypeMatcherIndicesOffset 270func (b *overloadBuilder) buildReturnType(o *sem.Overload) error { 271 if o.ReturnType != nil { 272 indices, err := b.collectMatcherIndices(*o.ReturnType) 273 if err != nil { 274 return err 275 } 276 b.returnTypeMatcherIndicesOffset = b.lut.matcherIndices.Add(indices) 277 } 278 return nil 279} 280 281// matcherIndex returns the index of TMatcher or NMatcher in 282// IntrinsicTable.TMatcher or IntrinsicTable.NMatcher, respectively. 283func (b *overloadBuilder) matcherIndex(n sem.Named) (int, error) { 284 switch n := n.(type) { 285 case *sem.Type, *sem.TypeMatcher: 286 if i, ok := b.TMatcherIndex[n]; ok { 287 return i, nil 288 } 289 return 0, fmt.Errorf("matcherIndex missing entry for %v %T", n.GetName(), n) 290 case *sem.TemplateTypeParam: 291 if i, ok := b.openTypeIndex[n]; ok { 292 return i, nil 293 } 294 return 0, fmt.Errorf("openTypeIndex missing entry for %v %T", n.Name, n) 295 case *sem.EnumMatcher: 296 if i, ok := b.NMatcherIndex[n]; ok { 297 return i, nil 298 } 299 return 0, fmt.Errorf("matcherIndex missing entry for %v %T", n.GetName(), n) 300 case *sem.TemplateEnumParam: 301 if i, ok := b.openNumberIndex[n]; ok { 302 return i, nil 303 } 304 return 0, fmt.Errorf("openNumberIndex missing entry for %v %T", n, n) 305 case *sem.TemplateNumberParam: 306 if i, ok := b.openNumberIndex[n]; ok { 307 return i, nil 308 } 309 return 0, fmt.Errorf("openNumberIndex missing entry for %v %T", n, n) 310 default: 311 return 0, fmt.Errorf("overload.matcherIndex() does not handle %v %T", n, n) 312 } 313} 314 315// collectMatcherIndices returns the full list of matcher indices required to 316// match the fully-qualified-name. For names that have do not have templated 317// arguments, collectMatcherIndices() will return a single TMatcher index. 318// For names that do have templated arguments, collectMatcherIndices() returns 319// a list of type matcher indices, starting with the target of the fully 320// qualified name, then followed by each of the template arguments from left to 321// right. Note that template arguments may themselves have template arguments, 322// and so collectMatcherIndices() may call itself. 323// The order of returned matcher indices is always the order of the fully 324// qualified name as read from left to right. 325// For example, calling collectMatcherIndices() for the fully qualified name: 326// A<B<C, D>, E<F, G<H>, I> 327// Would return the matcher indices: 328// A, B, C, D, E, F, G, H, I 329func (b *overloadBuilder) collectMatcherIndices(fqn sem.FullyQualifiedName) ([]int, error) { 330 idx, err := b.matcherIndex(fqn.Target) 331 if err != nil { 332 return nil, err 333 } 334 out := []int{idx} 335 for _, arg := range fqn.TemplateArguments { 336 indices, err := b.collectMatcherIndices(arg.(sem.FullyQualifiedName)) 337 if err != nil { 338 return nil, err 339 } 340 out = append(out, indices...) 341 } 342 return out, nil 343} 344 345// buildIntrinsicTable builds the IntrinsicTable from the semantic info 346func buildIntrinsicTable(s *sem.Sem) (*IntrinsicTable, error) { 347 b := intrinsicTableBuilder{ 348 IntrinsicTable: IntrinsicTable{ 349 Sem: s, 350 TMatcherIndex: map[sem.Named]int{}, 351 NMatcherIndex: map[sem.Named]int{}, 352 }, 353 } 354 b.lut.matcherIndices = lut.New(list.Wrap(&b.MatcherIndices)) 355 b.lut.openTypes = lut.New(list.Wrap(&b.OpenTypes)) 356 b.lut.openNumbers = lut.New(list.Wrap(&b.OpenNumbers)) 357 b.lut.parameters = lut.New(list.Wrap(&b.Parameters)) 358 b.lut.overloads = lut.New(list.Wrap(&b.Overloads)) 359 360 b.layoutMatchers(s) 361 362 for _, f := range s.Functions { 363 overloads := make([]Overload, len(f.Overloads)) 364 overloadDescriptions := make([]string, len(f.Overloads)) 365 for i, o := range f.Overloads { 366 overloadDescriptions[i] = fmt.Sprint(o.Decl) 367 var err error 368 if overloads[i], err = b.buildOverload(o); err != nil { 369 return nil, err 370 } 371 } 372 373 b.Functions = append(b.Functions, Function{ 374 OverloadDescriptions: overloadDescriptions, 375 NumOverloads: len(overloads), 376 OverloadsOffset: b.lut.overloads.Add(overloads), 377 }) 378 } 379 380 b.lut.matcherIndices.Compact() 381 b.lut.openTypes.Compact() 382 b.lut.openNumbers.Compact() 383 b.lut.parameters.Compact() 384 b.lut.overloads.Compact() 385 386 return &b.IntrinsicTable, nil 387} 388