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:

Create singly linked list in golang

A linked list is a linear data structure, in which the elements are linked to next element using pointers.

The following illustration would help to understand it:  

Let's implement this  in golang:

To create a linked listed we first have to create Node with data and next pointing to the another Node.

To create Node we need two fields, data and next.

Step1:

type Node struct{
   data int
   next *Node
}

Step2:

Now define Linkedlist struct:

type LinkedList struct{
   head *Node
}

Step3:

Now that we have defined structs that we need, let's try creating Node and linkedlist .

func main(){
   node1 := new(Node)
   fmt.Println(node1)
}

Here when we create new node it will have default values of each field which here is 0 and nil.
so printing node1 would give the output as:

&{0 <nil>}

We now need a way to initialise Node struct with our values.

Step4:

Writing a function to do this:

func (n *Node) NewNode(data int, next *Node){
   n.data = data
   n.next = next
}

Step5:

with this new function we will change the code in main() function

func main(){
   node1 := new(Node)
   fmt.Println(node1)
   node1.NewNode(1, nil)
   fmt.Println(node1)
}

Now we the second print statement gives node1 output as &{1 <nil>}

The reason that `next` field is showing it as nil is because we just created one Node and there is no other Node where we can link this node1 to.

Step6:

Let's created linkedlist with this Node:

func main(){
   node1 := new(Node)
   fmt.Println(node1)
   node1.NewNode(1, nil)
   fmt.Println(node1)
   llist := new(LinkedList)
   llist.head = node1
}

Now we have created linked list with it's head pointing to our Node1.

Our linked list would now be like this:

Step7:

Let's create Node2 and update our linkedlist.

func main(){
   node1 := new(Node)
   fmt.Println(node1)
   node1.NewNode(1, nil)
   fmt.Println(node1)
   llist := new(LinkedList)
   llist.head = node1
   node2 := new(Node)
   node2.NewNode(2, nil)
   llist.head.next = node2
}

The last three lines of code we have created new Node which is same as step5, 

now that we have to update our existing linkedlist the update that we have to do is head is pointing to Node1 i.e. head = Node1 now Node1.next has to be pointing to Node2.

Node1 is head here so head.next = node2 will update our linked list as below:

Step8:

For the last step let's create another Node and update our linked list:

func main(){
   node1 := new(Node)
   fmt.Println(node1)
   node1.NewNode(1, nil)
   fmt.Println(node1)
   llist := new(LinkedList)
   llist.head = node1
   node2 := new(Node)
   node2.NewNode(2, nil)
   llist.head.next = node2
   node3 := new(Node)
   node3.NewNode(3, nil)
   llist.head.next.next = node3
}

This will have our linked list as in first figure.

The complete code is:

Envoy with grpc Access logs

What is Envoy

Envoy is an L7 proxy and communication bus designed for large modern service oriented architectures. The project was born out of the belief that:

The network should be transparent to applications. When network and application problems do occur it should be easy to determine the source of the problem.

In practice, achieving the previously stated goal is incredibly difficult. Envoy attempts to do so by providing the following high level features:

More details about envoy documentation available at:  https://www.envoyproxy.io/docs/envoy/latest/about_docs

Now let's start implementing envoy as side-car along with our application containers and run it in a single pod:

This implementation is specific to kubernetes environment.

Envoy can be part of side car for any application and communication to application happens through envoy. Any inbound traffic will be done through envoy and envoy will have listeners , routing configured.

This can be done through grpcImplementations or with yaml configuration. These will be registered with envoy XDS Apis and envoy will know where to reach for communicating with application.

Here we will look at envoy yaml configuration:

envoy-grpcconfig.yaml

Here we have configured listeners , filters and routes.

Envoy Configuration:

Envoy is listening  at port 9902 in local host. This is where we can get /stats.

Application configuration:

In routes, we specified details of the cluster that matches with a pattern.

For each of the matching pattern envoy routes it to the cluster specified under virtual_hosts.Cluster details are specified under Clusters. The application will be served for this example with cluster name as service_c.

The host address and port details for service_c is where test application is served.

Grpc Access logs:

Under filters,we have specfied the configuration for access_log.

Here we are specifying it as envoy.http_grpc_access_log. Grpc Access logs details can. be found at

https://github.com/envoyproxy/envoy/blob/d90464cace696da61248d3999081c3c0d22a725b/api/envoy/data/accesslog/v2/accesslog.proto

More options on configuring access logs can be found at

https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/observability/access_logging

The yaml config emits access_logs for upstream systems.

Grpc AccessLogService Implementation:

For grpc we have to implement grpc server for AccessLogService.

Code is available at :https://github.com/sreesindhusruthiyadavalli/envoy-grpc/tree/master

Build the docker image and deploy it in a pod.

Please check kubernetes apply -f <deployment.yaml>/<service.yaml> for deployment and service configuration for any pod.I have given service name as 'envoy-grpc'.

Kubectl get services --> List of services available in kubernetes cluster.

It gives envoy-grpc as service name for grpc AccessLogService.

Now in envoy configuration we have to configure access logs which has to be communicated with the above service.

Under clusters give the service host address(envoy-grpc.default.svc.cluster.local) and add strict_dns to the access_log_cluster.

Build envoy with the yaml configuration and invoke an api inside the test application.

Enter into envoy pod: curl 127.0.0.1:8789/<resource>

This gives the response from the application.

Now check the logs of envoy-grpc pod.We will get to see the accesslog.

The Concept of Overfitting in Machine learning

If you are taking any Machine learning courses or practising to solve some ML problems.You would have come across this term called “Overfitting”.

Let’s try to understand it with a simple example:

We are trying to come up with a generic size of a T-shirt that suits an average person.(not extreme tall/short and weights).

And for that we got certain sample measurements from the existing population.

Now we have come up with certain values for hands, neck, back etc and designed a shirt.

Now based on the feedback received from each individual , we keep changing the measurements such that it fits just fine for people in the sample. 

The adjustments we are trying to make doesn’t generalise much as we are trying to make sure that the shirt fits  perfectly for the people who’s measurements are known.

using regular expression in sublime Text Editor

Sublime Text editor provides an easy way of replacing text using regular expressions.

Let's take a simple regex examples and replacing it with the values that we would like to have.

one of the sample text is :

"CreateTime" : ISODate("2018-12-21T15:10:30.145Z")

This has to be replaced with the value in the quotes.

We can do this using any of the programming language and use grouping and replace with the value.

The same can be done in sublime editor as well:

Just select Edit-->Replace.

Choose Regex mode

Select Replace All will do the job.

Intersection over union - Object detection

During object detection ,

When the image has more than one anchor box after filtering by thresholding over the classes scores , we use non-max suppression to get one anchor box for object detection.

Non-max suppression uses intersection over union.

Intersection over union calculates the intersection area of any two boxes by area of union of two boxes.

Here we have considered the  coordinates of each box which are diagonal like top left and bottom right

Our naming conventions here for each box  (x1,y1) – top left and (x2,y2) – bottom right.

Now for two boxes to calculate the intersection need to find the maximum for top left and minimum of bottom right.

X1_inter = max(box1(x1), box2(x1))

Y1_inter = max(box1(y1), box2(y1))

X2_inter = min(box1(x2), box2(x2))

Y2_inter = min(box1(y2), box2(y2))

Here is the code to implement iou: