Go Race Detector Implementation Challenge

Concurrency is a powerful feature in Go, but it introduces the risk of data races. A data race occurs when two or more goroutines access the same memory location concurrently, and at least one of the accesses is a write. This challenge asks you to implement a simplified version of a race detector for Go programs. Understanding and identifying data races is crucial for writing robust and reliable concurrent applications.

Problem Description

Your task is to build a tool that analyzes Go code to detect potential data races. This tool will simulate the execution of a Go program and monitor memory accesses to identify concurrent writes to the same memory location without proper synchronization.

Key Requirements:

1. Goroutine Simulation: The tool needs to simulate the execution of goroutines. For simplicity, we will assume a basic model of goroutine scheduling.
2. Memory Access Tracking: Track reads and writes to memory locations. Each memory location should be uniquely identifiable (e.g., by its address or an identifier).
3. Concurrency Detection: Detect when multiple goroutines are accessing the same memory location.
4. Race Condition Identification: Identify a data race if:
   • Two or more goroutines access the same memory location.
   • At least one of the accesses is a write.
   • There is no synchronization mechanism (like a mutex) protecting the access.
5. Reporting: Report detected data races, including the memory location, the goroutines involved, and the type of access (read/write).

Expected Behavior:

The tool will take a Go program as input (represented in a simplified format) and output a list of all detected data races. If no data races are found, it should indicate that.

Important Edge Cases:

• Atomic Operations: Consider how to handle atomic operations which, by definition, are safe for concurrent access. For this challenge, you can assume atomic operations are implicitly synchronized.
• Uninitialized Variables: Races on uninitialized variables are a common source of bugs.
• Global Variables vs. Local Variables: While both can be subject to races, global variables are often more susceptible due to their shared nature.

Examples

Example 1: Simple Write Race

Input:
Program:
package main

var global_var int

func main() {
    go func() {
        global_var = 10
    }()
    go func() {
        global_var = 20
    }()
}

Output:
Data Race Detected:
  Memory Location: global_var
  Goroutines: Goroutine-1, Goroutine-2
  Accesses: Write by Goroutine-1, Write by Goroutine-2
  Reason: Concurrent writes to the same memory location without synchronization.

Example 2: Read-Write Race

Input:
Program:
package main

var counter int

func main() {
    go func() {
        counter = 1
    }()
    go func() {
        _ = counter // Read
    }()
}

Output:
Data Race Detected:
  Memory Location: counter
  Goroutines: Goroutine-1, Goroutine-2
  Accesses: Write by Goroutine-1, Read by Goroutine-2
  Reason: Concurrent write and read to the same memory location without synchronization.

Example 3: No Race (Implicit Synchronization)

Input:
Program:
package main

var data int

func main() {
    go func() {
        data = 5 // Write
    }()
    // In a real scenario, a sync.WaitGroup or similar would be used here
    // to ensure the write completes before main exits. For this simulation,
    // we'll assume the goroutine has enough time to execute.
    // Assume main waits for Goroutine-1 to finish its operation.
}

Output:
No data races detected.

Constraints

• The input Go program will be a simplified representation. You will not be running actual Go code. Instead, you will process a structured description of the program's concurrency and memory accesses. This structured description will include:
  • A list of global variables and their initial values.
  • A definition of the main function, outlining goroutines launched.
  • For each goroutine, a sequence of operations (read or write to a specific memory location).
• Assume a maximum of 10 goroutines per program.
• Assume a maximum of 20 memory locations (variables) per program.
• Assume a maximum of 50 operations per goroutine.
• Synchronization primitives (like sync.Mutex or sync.WaitGroup) will be simplified. You can represent their effect in the input description (e.g., "lock acquired," "lock released," "barrier reached"). For this initial challenge, you can assume no explicit synchronization primitives are used in the provided input program descriptions.
• Performance is not a primary concern for this challenge, but your solution should be reasonably efficient for the given constraints.

Notes

This challenge is an exercise in understanding the logic behind race detection, not necessarily in building a full-fledged static or dynamic analysis tool.

You will need to define a data structure or format to represent the simplified Go programs for analysis. Consider how to map memory locations and goroutines to unique identifiers.

Think about how to model the state of memory and the execution flow of goroutines. A common approach for dynamic analysis is to log memory accesses and check for conflicts.

The core of the problem lies in managing the timeline of operations and checking for overlapping, unsynchronized accesses to shared memory.