alg.go

     1  // Copyright 2016 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package types
     6  
     7  import "cmd/compile/internal/base"
     8  
     9  // AlgKind describes the kind of algorithms used for comparing and
    10  // hashing a Type.
    11  type AlgKind int
    12  
    13  //go:generate stringer -type AlgKind -trimprefix A alg.go
    14  
    15  const (
    16  	ANOEQ AlgKind = iota
    17  	AMEM0
    18  	AMEM8
    19  	AMEM16
    20  	AMEM32
    21  	AMEM64
    22  	AMEM128
    23  	ASTRING
    24  	AINTER
    25  	ANILINTER
    26  	AFLOAT32
    27  	AFLOAT64
    28  	ACPLX64
    29  	ACPLX128
    30  
    31  	// Type can be compared/hashed as regular memory.
    32  	AMEM AlgKind = 100
    33  
    34  	// Type needs special comparison/hashing functions.
    35  	ASPECIAL AlgKind = -1
    36  )
    37  
    38  // AlgType returns the AlgKind used for comparing and hashing Type t.
    39  // If it returns ANOEQ, it also returns the component type of t that
    40  // makes it incomparable.
    41  func AlgType(t *Type) (AlgKind, *Type) {
    42  	if t.Noalg() {
    43  		return ANOEQ, t
    44  	}
    45  
    46  	switch t.Kind() {
    47  	case TANY, TFORW:
    48  		// will be defined later.
    49  		return ANOEQ, t
    50  
    51  	case TINT8, TUINT8, TINT16, TUINT16,
    52  		TINT32, TUINT32, TINT64, TUINT64,
    53  		TINT, TUINT, TUINTPTR,
    54  		TBOOL, TPTR,
    55  		TCHAN, TUNSAFEPTR:
    56  		return AMEM, nil
    57  
    58  	case TFUNC, TMAP:
    59  		return ANOEQ, t
    60  
    61  	case TFLOAT32:
    62  		return AFLOAT32, nil
    63  
    64  	case TFLOAT64:
    65  		return AFLOAT64, nil
    66  
    67  	case TCOMPLEX64:
    68  		return ACPLX64, nil
    69  
    70  	case TCOMPLEX128:
    71  		return ACPLX128, nil
    72  
    73  	case TSTRING:
    74  		return ASTRING, nil
    75  
    76  	case TINTER:
    77  		if t.IsEmptyInterface() {
    78  			return ANILINTER, nil
    79  		}
    80  		return AINTER, nil
    81  
    82  	case TSLICE:
    83  		return ANOEQ, t
    84  
    85  	case TARRAY:
    86  		a, bad := AlgType(t.Elem())
    87  		switch a {
    88  		case AMEM:
    89  			return AMEM, nil
    90  		case ANOEQ:
    91  			return ANOEQ, bad
    92  		}
    93  
    94  		switch t.NumElem() {
    95  		case 0:
    96  			// We checked above that the element type is comparable.
    97  			return AMEM, nil
    98  		case 1:
    99  			// Single-element array is same as its lone element.
   100  			return a, nil
   101  		}
   102  
   103  		return ASPECIAL, nil
   104  
   105  	case TSTRUCT:
   106  		fields := t.Fields()
   107  
   108  		// One-field struct is same as that one field alone.
   109  		if len(fields) == 1 && !fields[0].Sym.IsBlank() {
   110  			return AlgType(fields[0].Type)
   111  		}
   112  
   113  		ret := AMEM
   114  		for i, f := range fields {
   115  			// All fields must be comparable.
   116  			a, bad := AlgType(f.Type)
   117  			if a == ANOEQ {
   118  				return ANOEQ, bad
   119  			}
   120  
   121  			// Blank fields, padded fields, fields with non-memory
   122  			// equality need special compare.
   123  			if a != AMEM || f.Sym.IsBlank() || IsPaddedField(t, i) {
   124  				ret = ASPECIAL
   125  			}
   126  		}
   127  
   128  		return ret, nil
   129  	}
   130  
   131  	base.Fatalf("AlgType: unexpected type %v", t)
   132  	return 0, nil
   133  }
   134  
   135  // TypeHasNoAlg reports whether t does not have any associated hash/eq
   136  // algorithms because t, or some component of t, is marked Noalg.
   137  func TypeHasNoAlg(t *Type) bool {
   138  	a, bad := AlgType(t)
   139  	return a == ANOEQ && bad.Noalg()
   140  }
   141  
   142  // IsComparable reports whether t is a comparable type.
   143  func IsComparable(t *Type) bool {
   144  	a, _ := AlgType(t)
   145  	return a != ANOEQ
   146  }
   147  
   148  // IncomparableField returns an incomparable Field of struct Type t, if any.
   149  func IncomparableField(t *Type) *Field {
   150  	for _, f := range t.Fields() {
   151  		if !IsComparable(f.Type) {
   152  			return f
   153  		}
   154  	}
   155  	return nil
   156  }
   157  
   158  // IsPaddedField reports whether the i'th field of struct type t is followed
   159  // by padding.
   160  func IsPaddedField(t *Type, i int) bool {
   161  	if !t.IsStruct() {
   162  		base.Fatalf("IsPaddedField called non-struct %v", t)
   163  	}
   164  	end := t.width
   165  	if i+1 < t.NumFields() {
   166  		end = t.Field(i + 1).Offset
   167  	}
   168  	return t.Field(i).End() != end
   169  }
   170
View as plain text