validate.go

     1  // Copyright 2018 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 analysis
     6  
     7  import (
     8  	"fmt"
     9  	"reflect"
    10  	"strings"
    11  	"unicode"
    12  )
    13  
    14  // Validate reports an error if any of the analyzers are misconfigured.
    15  // Checks include:
    16  // that the name is a valid identifier;
    17  // that the Doc is not empty;
    18  // that the Run is non-nil;
    19  // that the Requires graph is acyclic;
    20  // that analyzer fact types are unique;
    21  // that each fact type is a pointer.
    22  //
    23  // Analyzer names need not be unique, though this may be confusing.
    24  func Validate(analyzers []*Analyzer) error {
    25  	// Map each fact type to its sole generating analyzer.
    26  	factTypes := make(map[reflect.Type]*Analyzer)
    27  
    28  	// Traverse the Requires graph, depth first.
    29  	const (
    30  		white = iota
    31  		grey
    32  		black
    33  		finished
    34  	)
    35  	color := make(map[*Analyzer]uint8)
    36  	var visit func(a *Analyzer) error
    37  	visit = func(a *Analyzer) error {
    38  		if a == nil {
    39  			return fmt.Errorf("nil *Analyzer")
    40  		}
    41  		if color[a] == white {
    42  			color[a] = grey
    43  
    44  			// names
    45  			if !validIdent(a.Name) {
    46  				return fmt.Errorf("invalid analyzer name %q", a)
    47  			}
    48  
    49  			if a.Doc == "" {
    50  				return fmt.Errorf("analyzer %q is undocumented", a)
    51  			}
    52  
    53  			if a.Run == nil {
    54  				return fmt.Errorf("analyzer %q has nil Run", a)
    55  			}
    56  			// fact types
    57  			for _, f := range a.FactTypes {
    58  				if f == nil {
    59  					return fmt.Errorf("analyzer %s has nil FactType", a)
    60  				}
    61  				t := reflect.TypeOf(f)
    62  				if prev := factTypes[t]; prev != nil {
    63  					return fmt.Errorf("fact type %s registered by two analyzers: %v, %v",
    64  						t, a, prev)
    65  				}
    66  				if t.Kind() != reflect.Ptr {
    67  					return fmt.Errorf("%s: fact type %s is not a pointer", a, t)
    68  				}
    69  				factTypes[t] = a
    70  			}
    71  
    72  			// recursion
    73  			for _, req := range a.Requires {
    74  				if err := visit(req); err != nil {
    75  					return err
    76  				}
    77  			}
    78  			color[a] = black
    79  		}
    80  
    81  		if color[a] == grey {
    82  			stack := []*Analyzer{a}
    83  			inCycle := map[string]bool{}
    84  			for len(stack) > 0 {
    85  				current := stack[len(stack)-1]
    86  				stack = stack[:len(stack)-1]
    87  				if color[current] == grey && !inCycle[current.Name] {
    88  					inCycle[current.Name] = true
    89  					stack = append(stack, current.Requires...)
    90  				}
    91  			}
    92  			return &CycleInRequiresGraphError{AnalyzerNames: inCycle}
    93  		}
    94  
    95  		return nil
    96  	}
    97  	for _, a := range analyzers {
    98  		if err := visit(a); err != nil {
    99  			return err
   100  		}
   101  	}
   102  
   103  	// Reject duplicates among analyzers.
   104  	// Precondition:  color[a] == black.
   105  	// Postcondition: color[a] == finished.
   106  	for _, a := range analyzers {
   107  		if color[a] == finished {
   108  			return fmt.Errorf("duplicate analyzer: %s", a.Name)
   109  		}
   110  		color[a] = finished
   111  	}
   112  
   113  	return nil
   114  }
   115  
   116  func validIdent(name string) bool {
   117  	for i, r := range name {
   118  		if !(r == '_' || unicode.IsLetter(r) || i > 0 && unicode.IsDigit(r)) {
   119  			return false
   120  		}
   121  	}
   122  	return name != ""
   123  }
   124  
   125  type CycleInRequiresGraphError struct {
   126  	AnalyzerNames map[string]bool
   127  }
   128  
   129  func (e *CycleInRequiresGraphError) Error() string {
   130  	var b strings.Builder
   131  	b.WriteString("cycle detected involving the following analyzers:")
   132  	for n := range e.AnalyzerNames {
   133  		b.WriteByte(' ')
   134  		b.WriteString(n)
   135  	}
   136  	return b.String()
   137  }
   138
View as plain text