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