Write your own Static analyzer in golang

Go tools provides a package go/analysis   for analyzing go code.  

The goal of this package as per it's documentation is :

A static analysis is a function that inspects a package of Go code and reports a set of diagnostics (typically mistakes in the code), and perhaps produces other results as well, such as suggested refactorings or other facts. An analysis that reports mistakes is informally called a "checker". For example, the printf checker reports mistakes in fmt.Printf format strings.

We will use this package to write a static analyzer of our own use case.

Use case that we are planning to do diagnostics of go code is to check if there are any unused Interface Types in the struct fields.

Example:

type Animal interface{

}

type Abstract interface{

}

type Test struct {
   err        error
   abc       Animal
}

End Goal:

Here the analyzer has to throw diagnostic error saying Abstract is unused.

To start with we will construct an analyzer with the fields as below:

var UnusedInterfaceAnalyzer = &analysis.Analyzer{
   Name: "checkUnusedAnalyzer",
   Doc: unusedIntDoc,
   Requires: []*analysis.Analyzer{inspect.Analyzer},
   Run: customrun,
}

Name is userdefined Name

Documentation helps to know what this analyzer checks for

For more details on this, check analyzer 

we now have to write the analyzer logic in the function customrun.

So defining the function 

func customrun(pass *analysis.Pass) (interface{}, error) {}

It takes pass as input, from the documentation pass, it does single unit of work. Here we have to write logic to check for unused interfaces.

In the pass struct we use ResultOf field. When driver runs the analyzers and make their results available in map which holds the results computed by the analyzers.

we will be using inspect package which provides an AST inspector for the syntax trees of a package.

func customrun(pass *analysis.Pass) (interface{}, error) {
   inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)

   inspect.Preorder(nil, func(n ast.Node) {
      
   }
   return nil, nil
}

the first parameter in preorder is used to filter out different types of ast nodes. Here we need TypeSpec , Interface Type and StructType.

defining a variable to filter ast.Nodes and passing this as first argument of preOrder function.

nodeFilter := []ast.Node{
   (*ast.InterfaceType)(nil),
   (*ast.TypeSpec)(nil),
   (*ast.StructType)(nil),
}

this filter is sent as input to the inspector so that the preorder logic gets exeucted only for these Node types.

Now in the preorder logic, I am first storing all the interface Types into a map.

intfMaps := make(map[string]int)
inspect.Preorder(nodeFilter, func(n ast.Node) {
   switch t := n.(type){
   case *ast.TypeSpec:
      // which are public
      if t.Name.IsExported() {
         switch t.Type.(type) {
         // and are interfaces
         case *ast.InterfaceType:
            intfMaps[t.Name.Name] = 1
         }
      }

Now for the struct types, if we find any field that is using Interface will delete the key in the map.

By the time we parse all the struct types, we will have map that are unused Interfaces.

Let's see  the updated code now:

inspect.Preorder(nodeFilter, func(n ast.Node) {
   switch t := n.(type){
   case *ast.TypeSpec:
      // which are public
      if t.Name.IsExported() {
         switch t.Type.(type) {
         // and are interfaces
         case *ast.InterfaceType:
            intfMaps[t.Name.Name] = 1
         }
      }
   case *ast.StructType:
      for _, field := range t.Fields.List {
         switch field.Type.(type){
         case *ast.Ident:
            identName := field.Type.(*ast.Ident).Name
            //Remove interfaces which are used
            for k := range intfMaps{
               if identName == k{
                  delete(intfMaps, k)
               }
            }
         }
      }
   }
})

For each struct type, we will loop through each field in the struct 

For each field get the field Type and if it matches the map intfMaps , delete the key so that map gets updated with unused Interface types.

After this we now have to loop through the intfMaps and send diagnostic report if map is not empty.

inspect.Preorder(nil, func(n ast.Node) {
   switch t := n.(type){
   case *ast.StructType:
      for x := range intfMaps {
         pass.Reportf(t.Pos(), "unused Interface %s", x)
      }
   }
})

Here if map has keys , the analyzer will throw diagnostic report as below:

unexpected diagnostic: unused Interface Abstract.

Testing:

For testing this code analysis  has analysistest package. We need to have test data package which has our go code for which we want to test the analyzer on.

The repo hierarchy is like this:

In the test data folder, created a go file with the example data shared above.

In customsa_test.go has :

import (
   "golang.org/x/tools/go/analysis/analysistest"
   "testing"
)

func TestCtxArg(t *testing.T) {
   analysistest.Run(t, analysistest.TestData(), Analyzer)
}

when I run go test.

the output is :

unexpected diagnostic: unused Interface Abstract.

Complete code is available at:

CustomStaticAnalyzer

Implementation of stack data structure in golang (without using builtin len)

Implementation of stack data structure in go. 

Stack data structure follows LIFO order which is LastInFirstOut, which means element entered last will be out first.

Examples of stack in real life:

Stack of pancakes which are piled up.

The last pancake which is at the top is the first one to be taken out.

Stack data structures consists of two fields to maintain the data: 

Top element of the stack,
List of elements in the stack.

To make use of this data structure we need a way to push any new element to the stack, remove an element from existing stack, update the top values accoridngly.

Two more useful functions that helps when we are working with stack is to know what is the current top element and wherther stack is empty or not.

From the above discussion we need four different functions on Stack.

Push() ---> To push data to the stack and update the top value.

Pop()--> To remove the top element and update the top value.

Peek()--> To return the top value, this doesn't change the current stack.

isEmpty()--> Check if stack is empty or not.

Implementation of stack in golang:

To start with create a struct with the name with two fields top and list of elements which is slice in go.

type Stack struct{
   top int
   slice []int
}

Initialize the struct, writing function for the same:

func (s *Stack) NewStack(){
   s.top = -1
   s.slice = make([]int,0)
}

Let's proceed with pushing an element to the stack, our slice is list of integer types, so we will push only integers to this stack.

PUSH():

func (s *Stack) Push(x int){
      s.slice = append(s.slice, x)
      s.top++
   
}

All that we want to do in push is append the element to the list, if it's a new one slice will be of size 0, so appending this will add it as the first element. Increment the top value.

Each element gets stored in a memory location and given finite memory locations we can't keep pushing infinite elements to stack. We need a cap on the top value and throw an error if we are out of memory.

Consider we have unsigned int get the max value of unsigned int as below:

const MaxUint = ^uint(0)
const MAX_SIZE = int(MaxUint >> 1)

Now while we push the data we need to check if top value is with in the MAX_SIZE.

Updating the push function:

func (s *Stack) Push(x int){
   if s.top > MAX_SIZE - 1 {
      fmt.Println("Stack overflow")
   } else{
      s.slice = append(s.slice, x)
      s.top++
   }
}

This throws error incase top exceeds MAX_SIZE.

Pop():

func (s *Stack) Pop(){
      s.slice = s.slice[:s.top]
      s.top--
      fmt.Printf("slice %+v, top %d", s.slice,s.top)
}

Update the slice by removing the last inserted element and decrement the top by 1.

We can return the element that has  been removed so let's update the pop function.

func (s *Stack) Pop() int{
      x = s.slice[s.top]
      s.slice = s.slice[:s.top]
      s.top--
      fmt.Printf("slice %+v, top %d", s.slice,s.top)
   
   return x
}

We need a way to know that stack doesn;t have any more elements to pop, update the pop function with this check.

If top value is less than 0 then throw error where we can no longer pop any elements from the stack.

func (s *Stack) Pop() int{
   var x int
   if s.top < 0{
      fmt.Println("Stack underflow")
      return -1
   } else{
      x = s.slice[s.top]
      s.slice = s.slice[:s.top]
      s.top--
      fmt.Printf("slice %+v, top %d", s.slice,s.top)
   }
   return x
}

Peek():

We need to return the top element in the stack, the difference between Peek and Pop is ,

In Pop we update the stack by removing the top element,
In peek we just read the data from the stack.

Implementation is same as Pop except updating the stack.

func (s *Stack) Peek() int{
   var x int
   if s.top < 0 {
      fmt.Println("Stack underflow")
      return 0
   } else{
      x = s.slice[s.top]
   }
   return x
}

isEmpty():

Check if the stack is empty based on the top value, if it's less than 0 stack is empty.

func (s *Stack) isEmpty() bool{
   return s.top < 0
}

Complete code is available here:

Insert element in linkedlist - Implement in go

 This is 4th post on linked list, for previous post on linkedlist, please check posts from :

https://sreesindhusruthi.blogspot.com/2021/07/create-single-linked-list-in-golang.html

Insert is the function name to insert nodes in linked list:

func (ll *LinkedList) Insert(data int, position int){ }

Step1:  We need to have a Node with the data given. 

temp := new(Node)
temp.data = data

Step2: If linked list is empty then insert the temp Node as head of the linked list.

//This inserts new element as linked list is empty
if ll.head == nil{
   ll.head = temp
   return
}

Step3: If position is 0 then we need to update the linkedlist head to temp Node and update the current linked list reference.

//This inserts at beginning of the linked list.
if position == 0{
   temp.next = ll.head
   ll.head = temp
}

Step4: Loop till we reach the position we want to Insert  the Node, we need a variable currentNode to traverse till the desired position, update the currentNode for each iteration of the loop, we will compare the position with currentposition.

var currPosition int
currentNode := ll.head

for currPosition < position-1 && currentNode != nil {
   currentNode = currentNode.next
   currPosition ++
   //fmt.Println(currentNode.data, currPosition)
}

Step5: Once we are at the postion where we have to Insert the node update the linked list references.

Example linked list : 3-->7-->10-->NULL
ll.Insert(4, 2)
Expected output is : 3--> 7--> 4-->10--> NULL

To acheive expected output store Node with data 10 into existingNextNode.

existingNextNode := currentNode.next

Update currentNode links 7--> 4 .

currentNode.next = temp

then traverse currentNode from 7 to 4.

currentNode = currentNode.next

update currentNode next to existingNextNode 4-->10

currentNode.next = existingNextNode

//Update the links
existingNextNode := currentNode.next
currentNode.next = temp
currentNode = currentNode.next
currentNode.next = existingNextNode

Full code:

Print elements of linkedlist - Golang

 This is 3rd post on linked list. For previous posts, pls check the links below:

https://sreesindhusruthi.blogspot.com/2021/07/create-single-linked-list-in-golang.html

https://sreesindhusruthi.blogspot.com/2021/07/length-of-linkedlist-implementation-in.html

Writing print function for linked list to print elements.

The function name is Print and elements data is available in Node.data .

Step1: Check if linked list is empty. If empty print "NULL"

Step2: Print Node.data and update head to next Node in the linkedlist.

The function code is :

func (ll *LinkedList) Print() {
   if ll.head == nil{
      fmt.Print("NULL")
      return
   }
   //No Intermediate variable is used so we are traversing on
   //the actual object created and it's references gets updated on updating ll.head.
   for ll.head != nil {
      fmt.Printf("%+v -->",ll.head.data)
      ll.head = ll.head.next
      ll.Print()
   }
}

Complete code:

Length of linkedlist - Implementation in golang

 To get started with linkedlist please check previous post on how to create singly linkedlist:

Link is as below:

https://sreesindhusruthi.blogspot.com/2021/07/create-single-linked-list-in-golang.html

Now that we have linked list, let's add function to get the length of the linked list.

In previous post we have Node and LinkedList structs created. 

Writing function for length.

func (ll *LinkedList) Len() int{ }

This is the function defintion takes linkedlist as input and integer as return type.

Let's write the logic 

Step1: Intialize variable with count variable. count := 0

Step2: Check if linkedlist is empty.  If it's empty then we return the count as 0.

count := 0
if ll.head == nil{
    return 0
}

Step3: As we have to traverse through linked list we need a variable to traverse to each Node.

count := 0
var temp *Node
if ll.head == nil{
   return 0
}
temp = ll.head

Step4: we need to loop till there are no more nodes in linkedlist. so the check would be 

    for temp != nil {}

Step5: now our temp is pointing to head and it;s not nil so will go into the loop, increment the count value, now update temp to next Node of head. 

for temp != nil {
   count ++
   temp = temp.next
   fmt.Println(temp)
}

Prints are added for checking if temp is getting updated as expected.

Complete code of this is: