Repository: mgechev/revive

Issue:
Detect looping over a `map` to compare its key exactly
**Is your feature request related to a problem? Please describe.**
In a recent code change, we modified a variable from a slice to a map:
```
-       TagIDs             []string
+       TagIDs             map[string]float64
```
but a loop across the now-map was changed in an obvious but inefficient way:
```
-       for _, id := range a.TagIDs {
+       for id := range a.TagIDs {
                if id == someStaticValue {
                        return nil
                }
        }
```
given that is now a map there's a really direct way to do that test.

**Describe the solution you'd like**
The linter should flag the loop or suggest a fix to make it:
```
if _, exists := a.TagIDs[someStaticValue]; exists {
    return nil
}
```

**Describe alternatives you've considered**
This isn't a correctness issue, just inefficiency, so when in doubt it shouldn't be too picky.

**Additional context**
This happens remarkably often in my experience for people new to Go or who are making scattered changes and don't always think too deeply about fixing the resulting compilation errors as they focus on the end goal.  None of the `golangci-lint` linters or current version of `revive` tripped on that loop as anything of note, but it is also more of a learning opportunity for the programmer rather than anything wrong necessarily with the program.

Discussion:
@alexandear: Thanks for the suggestion!

While the idea makes sense from an efficiency and readability perspective, this type of pattern—looping over a map to check for the presence of a single key—is more of a performance/style concern than a correctness issue. Introducing a rule for this case may lead to false positives or overly opinionated suggestions.


That said, this could be a great candidate for a more targeted static analysis tool or as a custom rule in projects where this pattern is a common pain point.

@ccoVeille @chavacava what do you think?@gannett-ggreer: It is similar in a sense to linters that say "you're not using any %-formatting codes in `fmt.Errorf`, you should use `errors.New` instead".

For example:
```
authoring/embed.go:40:11: use-errors-new: replace fmt.Errorf by errors.New (revive)
			Err:   fmt.Errorf("no body found for embed"),
```@ccoVeille: I'm fine with having the rule described in the issue in revive@chavacava: `revive` already has (too many?) "style-related" (enforce-*, max-*, ...) rules, one more or one less will not change affairs so why not.

The rule will need type information (to recognise loops over maps)@chavacava: The branch [rule/inefficient-map-lookup](https://github.com/mgechev/revive/tree/rule/inefficient-map-lookup) implements a draft of the rule `inefficient-map-lookup` that aims to handle the use case described in this issue.

The rule looks for ranges on map keys where the body is just one if on the key. If the range body has more than one statement the rule will not check it.

Some findings of the rule on public repositories:

https://github.com/open-policy-agent/opa/blob/f77322b3fb8ba5555adc6493e120a205dd2860a7/v1/bundle/keys.go#L54-L59

https://github.com/golang/tools/blob/6ebfec2837bbfbbdc5d3a9fe087c70c29be27fbf/go/packages/golist.go#L315-L321

@gannett-ggreer could you please check if the rule draft copes with your case?@gannett-ggreer: Yes, it works for the original code case I mentioned.

Solution patch:
diff --git a/README.md b/README.md
index 348d3b6..cc02ea0 100644
--- a/README.md
+++ b/README.md
@@ -560,6 +560,7 @@ List of all available rules. The rules ported from `golint` are left unchanged a
 | [`imports-blocklist`](./RULES_DESCRIPTIONS.md#imports-blocklist)   | []string | Disallows importing the specified packages                     |    no    |  no   |
 | [`increment-decrement`](./RULES_DESCRIPTIONS.md#increment-decrement) |  n/a   | Use `i++` and `i--` instead of `i += 1` and `i -= 1`.            |   yes    |  no   |
 | [`indent-error-flow`](./RULES_DESCRIPTIONS.md#indent-error-flow)   |  []string   | Prevents redundant else statements.                              |   yes    |  no   |
+| [`inefficient-map-lookup`](./RULES_DESCRIPTIONS.md#inefficient-map-lookup)   |  n/a  | Spots iterative searches for a key in a map           |   no    |  yes   |
 | [`line-length-limit`](./RULES_DESCRIPTIONS.md#line-length-limit)   | int (defaults to 80) | Specifies the maximum number of characters in a line             |    no    |  no   |
 | [`max-control-nesting`](./RULES_DESCRIPTIONS.md#max-control-nesting) |  int (defaults to 5)  | Sets restriction for maximum nesting of control structures. |    no    |  no   |
 | [`max-public-structs`](./RULES_DESCRIPTIONS.md#max-public-structs)  |  int (defaults to 5)  | The maximum number of public structs in a file.                  |    no    |  no   |
diff --git a/RULES_DESCRIPTIONS.md b/RULES_DESCRIPTIONS.md
index fe4f354..2c47500 100644
--- a/RULES_DESCRIPTIONS.md
+++ b/RULES_DESCRIPTIONS.md
@@ -56,6 +56,7 @@ List of all available rules.
 - [imports-blocklist](#imports-blocklist)
 - [increment-decrement](#increment-decrement)
 - [indent-error-flow](#indent-error-flow)
+- [inefficient-map-lookup](#inefficient-map-lookup)
 - [line-length-limit](#line-length-limit)
 - [max-control-nesting](#max-control-nesting)
 - [max-public-structs](#max-public-structs)
@@ -865,6 +866,50 @@ arguments = ["preserveScope"]
 arguments = ["preserve-scope"]
 ```
 
+## inefficient-map-lookup
+
+_Description_: This rule identifies code that iteratively searches for a key in a map.
+
+This inefficiency is usually introduced when refactoring code from using a slice to a map.
+For example if during refactoring the `elements` slice is transformed into a map.
+
+```diff
+-       elements             []string
++       elements             map[string]float64
+```
+
+and then a loop over `elements` is changed in an obvious but inefficient way:
+
+```diff
+-       for _, e := range elements {
++       for e := range elements {
+                if e == someStaticValue {
+                        // do something
+                }
+        }
+```
+
+Example:
+
+```go
+aMap := map[string]bool{}{}
+aValue := false
+
+// Inefficient map lookup
+for k := range aMap {
+  if k == aValue {
+    // do something
+  }
+}
+
+// Simpler and more efficient version
+if _, ok := aMap[aValue]; ok {
+  // do something
+}
+```
+
+_Configuration_: N/A
+
 ## line-length-limit
 
 _Description_: Warns in the presence of code lines longer than a configured maximum.
diff --git a/config/config.go b/config/config.go
index e03d337..22b2d67 100644
--- a/config/config.go
+++ b/config/config.go
@@ -113,6 +113,7 @@ var allRules = append([]lint.Rule{
 	&rule.PackageDirectoryMismatchRule{},
 	&rule.UseWaitGroupGoRule{},
 	&rule.UnsecureURLSchemeRule{},
+	&rule.InefficientMapLookupRule{},
 }, defaultRules...)
 
 // allFormatters is a list of all available formatters to output the linting results.
diff --git a/rule/inefficient_map_lookup.go b/rule/inefficient_map_lookup.go
new file mode 100644
index 0000000..6a92e14
--- /dev/null
+++ b/rule/inefficient_map_lookup.go
@@ -0,0 +1,169 @@
+package rule
+
+import (
+	"fmt"
+	"go/ast"
+	"go/token"
+	"strings"
+
+	"github.com/mgechev/revive/internal/astutils"
+	"github.com/mgechev/revive/lint"
+)
+
+// InefficientMapLookupRule spots potential inefficient map lookups.
+type InefficientMapLookupRule struct{}
+
+// Apply applies the rule to given file.
+func (*InefficientMapLookupRule) Apply(file *lint.File, _ lint.Arguments) []lint.Failure {
+	var failures []lint.Failure
+
+	onFailure := func(failure lint.Failure) {
+		failures = append(failures, failure)
+	}
+
+	w := &lintInefficientMapLookup{
+		file:      file,
+		onFailure: onFailure,
+	}
+
+	if err := file.Pkg.TypeCheck(); err != nil {
+		return []lint.Failure{
+			lint.NewInternalFailure(fmt.Sprintf("Unable to type check file %q: %v", file.Name, err)),
+		}
+	}
+
+	// Iterate over declarations looking for function declarations
+	for _, decl := range file.AST.Decls {
+		fn, ok := decl.(*ast.FuncDecl)
+		if !ok {
+			continue // not a function
+		}
+
+		if fn.Body == nil {
+			continue // external (no-Go) function
+		}
+
+		// Analyze the function body
+		ast.Walk(w, fn.Body)
+	}
+
+	return failures
+}
+
+// Name returns the rule name.
+func (*InefficientMapLookupRule) Name() string {
+	return "inefficient-map-lookup"
+}
+
+type lintInefficientMapLookup struct {
+	file      *lint.File
+	onFailure func(lint.Failure)
+}
+
+func (w *lintInefficientMapLookup) Visit(node ast.Node) ast.Visitor {
+	// Only interested in blocks of statements
+	block, ok := node.(*ast.BlockStmt)
+	if !ok {
+		return w // not a block of statements
+	}
+
+	w.analyzeBlock(block)
+
+	return w
+}
+
+// analyzeBlock searches AST subtrees with the following form
+//
+//	for <key> := range <map> {
+//		if <key> == <something> {
+//		   ...
+//		}
+func (w *lintInefficientMapLookup) analyzeBlock(b *ast.BlockStmt) {
+	for _, stmt := range b.List {
+		if !w.isRangeOverMapKey(stmt) {
+			continue
+		}
+
+		rangeOverMap := stmt.(*ast.RangeStmt)
+		key := rangeOverMap.Key.(*ast.Ident)
+
+		// Here we have identified a range over the keys of a map
+		// Let's check if the range body is
+		// { if <key> == <something> { ... } }
+		// or
+		// { if <key> != <something> { continue } ... }
+		if !isKeyLookup(key.Name, rangeOverMap.Body) {
+			continue
+		}
+
+		w.onFailure(lint.Failure{
+			Confidence: 1,
+			Node:       rangeOverMap,
+			Category:   lint.FailureCategoryCodeStyle,
+			Failure:    "inefficient lookup of map key",
+		})
+	}
+}
+
+func isKeyLookup(keyName string, blockStmt *ast.BlockStmt) bool {
+	blockLen := len(blockStmt.List)
+	if blockLen == 0 {
+		return false // empty
+	}
+
+	firstStmt := blockStmt.List[0]
+	ifStmt, ok := firstStmt.(*ast.IfStmt)
+	if !ok {
+		return false // the first statement of the body is not an if
+	}
+
+	binExp, ok := ifStmt.Cond.(*ast.BinaryExpr)
+	if !ok {
+		return false // the if condition is not a binary expression
+	}
+
+	if !astutils.IsIdent(binExp.X, keyName) {
+		return false // the if condition is not <key> <bin-op> <LHS>
+	}
+
+	switch binExp.Op {
+	case token.EQL:
+		// if key == ... should be the single statement in the block
+		return blockLen == 1
+
+	case token.NEQ:
+		// if key != ...
+		ifBodyStmts := ifStmt.Body.List
+		if len(ifBodyStmts) < 1 {
+			return false // if key != ... { /* empty */ }
+		}
+
+		branchStmt, ok := ifBodyStmts[0].(*ast.BranchStmt)
+		if !ok || branchStmt.Tok != token.CONTINUE {
+			return false // if key != ... { <not a continue> }
+		}
+
+		return true
+	}
+
+	return false
+}
+
+func (w *lintInefficientMapLookup) isRangeOverMapKey(stmt ast.Stmt) bool {
+	rangeStmt, ok := stmt.(*ast.RangeStmt)
+	if !ok {
+		return false // not a range
+	}
+
+	// Check if we range only on key
+	// for key := range ...
+	// for key, _ := range ...
+	hasValueVariable := rangeStmt.Value != nil && !astutils.IsIdent(rangeStmt.Value, "_")
+	if hasValueVariable {
+		return false // range over both key and value
+	}
+
+	// Check if we range over a map
+	t := w.file.Pkg.TypeOf(rangeStmt.X)
+	return t != nil && strings.HasPrefix(t.String(), "map[")
+}



Test patch:
diff --git a/test/inefficient_map_lookup_test.go b/test/inefficient_map_lookup_test.go
new file mode 100644
index 0000000..35a48d0
--- /dev/null
+++ b/test/inefficient_map_lookup_test.go
@@ -0,0 +1,12 @@
+package test
+
+import (
+	"testing"
+
+	"github.com/mgechev/revive/lint"
+	"github.com/mgechev/revive/rule"
+)
+
+func TestInefficientMapLookup(t *testing.T) {
+	testRule(t, "inefficient_map_lookup", &rule.InefficientMapLookupRule{}, &lint.RuleConfig{})
+}
diff --git a/testdata/inefficient_map_lookup.go b/testdata/inefficient_map_lookup.go
new file mode 100644
index 0000000..0c4b874
--- /dev/null
+++ b/testdata/inefficient_map_lookup.go
@@ -0,0 +1,63 @@
+package fixtures
+
+import "fmt"
+
+func inefficientMapLookup() {
+	type aS struct {
+		TagIDs map[int]string
+	}
+	a := aS{}
+	someStaticValue := 1
+	// use case from issue #1447
+	for id := range a.TagIDs { // MATCH /inefficient lookup of map key/
+		if id == someStaticValue {
+			return
+		}
+	}
+
+	for key, _ := range a.TagIDs { // MATCH /inefficient lookup of map key/
+		if key == someStaticValue {
+			return
+		}
+	}
+
+	for key, _ := range a.TagIDs { // MATCH /inefficient lookup of map key/
+		if key != someStaticValue {
+			continue
+		}
+		fmt.Println(key)
+	}
+
+	// do not match if the loop body contains more than
+	// just an if statement on the map key
+	aMap := map[int]int{}
+	for k := range aMap {
+		fmt.Println(k)
+		if k == 1 {
+			return
+		}
+	}
+
+	for k := range aMap {
+		if k == 1 {
+			return
+		}
+		fmt.Println(k)
+	}
+
+	// do not match on ranges over types other than maps
+	slice := []int{}
+	for i, _ := range slice {
+		if i == 1 {
+			fmt.Print(i)
+		}
+	}
+
+	for key, _ := range a.TagIDs {
+		if key != someStaticValue { // do not match if the loop body does more than just continuing
+			fmt.Println(key)
+			continue
+		}
+		fmt.Println(key)
+	}
+}