Documentation
¶
Overview ¶
imcs_algorithm.go
Index ¶
- Variables
- type CompletedTest
- type Engine
- func (e *Engine) AddCandidates(additions sets.Set)
- func (e *Engine) GetActiveTestPlan() *TestPlan
- func (e *Engine) GetCurrentState() SearchState
- func (e *Engine) GetCurrentTestPlan() (*TestPlan, error)
- func (e *Engine) GetEstimatedMaxTests() int
- func (e *Engine) GetExecutionLog() *ExecutionLog
- func (e *Engine) GetPendingAdditions() sets.Set
- func (e *Engine) GetStepCount() int
- func (e *Engine) InvalidateActivePlan()
- func (e *Engine) MergePendingAdditions()
- func (e *Engine) PlanNextTest() (*TestPlan, error)
- func (e *Engine) Reconcile(validCandidates sets.Set) (changed bool)
- func (e *Engine) RemoveCandidates(removals sets.Set)
- func (e *Engine) SubmitTestResult(result TestResult) error
- func (e *Engine) Undo() (*UndoFrame, bool)
- func (e *Engine) WasLastTestVerification() bool
- type ExecutionLog
- type IMCSAlgorithm
- type SearchState
- type SearchStep
- type TestPlan
- type TestResult
- type UndoFrame
- type UndoStack
Constants ¶
This section is empty.
Variables ¶
Functions ¶
This section is empty.
Types ¶
type CompletedTest ¶
type CompletedTest struct {
Plan TestPlan
Result TestResult
StateBeforeTest SearchState
}
CompletedTest is a record of a test that was planned and executed.
type Engine ¶
type Engine struct {
// contains filtered or unexported fields
}
Engine orchestrates the bisection search, owning the state and using the stateless algorithm to advance it.
func NewEngine ¶
func NewEngine(initialState SearchState) *Engine
NewEngine creates a new search orchestrator.
func (*Engine) AddCandidates ¶
AddCandidates safely adds a set of new items to the main candidate pool for future bisection iterations.
func (*Engine) GetActiveTestPlan ¶
GetActiveTestPlan returns the plan currently being tested.
func (*Engine) GetCurrentState ¶
func (e *Engine) GetCurrentState() SearchState
GetCurrentState returns a read-only view of the current search state.
func (*Engine) GetCurrentTestPlan ¶
GetCurrentTestPlan returns the active test plan if one is in progress. If no test is running, it returns a preview of the next plan to be executed. Returns nil if the search is complete.
func (*Engine) GetEstimatedMaxTests ¶
GetEstimatedMaxTests provides an estimated upper bound for the total tests. This estimate increases as more problems are found, which is intended.
func (*Engine) GetExecutionLog ¶
func (e *Engine) GetExecutionLog() *ExecutionLog
GetExecutionLog provides access to the log of completed tests.
func (*Engine) GetPendingAdditions ¶
GetPendingAdditions returns the items that will be added to the search at the end of the current iteration
func (*Engine) GetStepCount ¶
GetStepCount returns the number of committed steps in the current search path. This is the correct value to display to the user as the current progress.
func (*Engine) InvalidateActivePlan ¶
func (e *Engine) InvalidateActivePlan()
InvalidateActivePlan cancels any in-progress test plan, usually due to an external state change that makes the test irrelevant.
func (*Engine) MergePendingAdditions ¶
func (e *Engine) MergePendingAdditions()
MergePendingAdditions merges any deferred items into the main candidate pool. This is called at safe-boundary points, like the end of an iteration or a manual reset.
func (*Engine) PlanNextTest ¶
PlanNextTest commits to the next test plan, changing the process state to "awaiting result". This is a non-idempotent action.
func (*Engine) Reconcile ¶
Reconcile intelligently synchronizes the engine's internal state with a new set of valid candidates from an external source. It returns true if any internal state (active plan, pending additions, etc.) was modified.
func (*Engine) RemoveCandidates ¶
RemoveCandidates safely prunes a set of items from all aspects of the current search state, including the candidate list, conflict set, stable set, and any in-progress bisection steps on the search stack.
func (*Engine) SubmitTestResult ¶
func (e *Engine) SubmitTestResult(result TestResult) error
SubmitTestResult provides the result for the active test, advancing the search. It implicitly operates on the currently active plan.
func (*Engine) Undo ¶
Undo reverts to the previous state in the search. It returns the state that was just popped from the undo stack, allowing the caller to inspect the change that was undone
func (*Engine) WasLastTestVerification ¶
WasLastTestVerification checks if the most recently completed test was the final verification step.
type ExecutionLog ¶
type ExecutionLog struct {
// contains filtered or unexported fields
}
ExecutionLog records a linear history of all completed tests for display.
func NewExecutionLog ¶
func NewExecutionLog() *ExecutionLog
NewExecutionLog creates a new, empty log.
func (*ExecutionLog) Append ¶
func (el *ExecutionLog) Append(other *ExecutionLog)
Append appends another execution log to the current one.
func (*ExecutionLog) GetEntries ¶
func (el *ExecutionLog) GetEntries() []CompletedTest
GetEntries returns a copy of all recorded entries.
func (*ExecutionLog) GetLastTest ¶
func (el *ExecutionLog) GetLastTest() (CompletedTest, bool)
GetLastTest returns the most recently completed test, if one exists.
func (*ExecutionLog) Log ¶
func (el *ExecutionLog) Log(test CompletedTest)
Log adds a new completed test to the log.
type IMCSAlgorithm ¶
type IMCSAlgorithm struct{}
IMCSAlgorithm contains the pure, stateless logic for the bisection search.
func NewIMCSAlgorithm ¶
func NewIMCSAlgorithm() *IMCSAlgorithm
NewIMCSAlgorithm creates a new algorithm instance.
func (*IMCSAlgorithm) ApplyResult ¶
func (a *IMCSAlgorithm) ApplyResult(state SearchState, plan TestPlan, result TestResult) SearchState
ApplyResult takes a state, a completed test plan, and its result, and returns the new, updated state. This is a pure function.
func (*IMCSAlgorithm) PlanNextTest ¶
func (a *IMCSAlgorithm) PlanNextTest(state SearchState) (*TestPlan, error)
PlanNextTest determines the next test to run based on the current state. This logic now directly mirrors the decision points in the formal IMCS algorithm.
type SearchState ¶
type SearchState struct {
// Round is the top-level enumeration count, tracking how many independent conflict sets have been found.
Round int
// ConflictSet contains mods already identified as part of the minimal conflict set.
ConflictSet sets.Set
// Candidates is the global pool of mods remaining to be searched for conflicts.
// This set only shrinks when a new element is added to ConflictSet.
Candidates []string
// StableSet is the set of mods globally proven to be "good" and not part of any
// conflict. It grows as bisections on candidate sets result in GOOD.
StableSet sets.Set
// Iteration is the count of conflict elements being searched for within the current round (e.g., finding the 2nd element in a 3-mod conflict).
Iteration int
// Step counts tests within the current FindNextConflictElement (bisection) run.
// It resets at the start of each new FindNextConflictElement iteration.
Step int
// SearchStack is an iterative implementation of the recursive "FindNextConflictElement"
// procedure. Each SearchStep on the stack is a snapshot of a recursive call's arguments
// (the local stable set and local candidates for that bisection).
SearchStack []SearchStep
// IsVerifyingConflictSet is true if the next test planned should be the final `test(ConflictSet)` optimization step.
IsVerifyingConflictSet bool
// AllModIDs is the universe of all mods, used for context and resetting candidates.
AllModIDs []string
// IsComplete is true if the search has concluded and no more tests are needed.
IsComplete bool
// LastFoundElement stores the ID of the most recently discovered conflict element.
LastFoundElement string
// LastTestResult stores the outcome of the test that produced this state.
LastTestResult TestResult
}
SearchState (renamed from SearchSnapshot) represents a complete, immutable state of the conflict search.
func NewInitialState ¶
func NewInitialState() SearchState
NewInitialState creates the starting state for a new search.
func (SearchState) GetCandidateSet ¶
func (s SearchState) GetCandidateSet() (candidates sets.Set)
GetCandidateSet determines the current StableSet based on the state.
func (SearchState) GetClearedSet ¶
func (s SearchState) GetClearedSet() (cleared sets.Set)
GetClearedSet calculates the implicit ClearedSet
func (SearchState) GetCurrentStep ¶
func (s SearchState) GetCurrentStep() (SearchStep, bool)
GetCurrentStep returns the top of the search stack, which represents the state of the current "FindNextConflictElement" bisection.
func (SearchState) GetStableSet ¶
func (s SearchState) GetStableSet() (stable sets.Set)
GetStableSet determines the current StableSet based on the state.
type SearchStep ¶
type SearchStep struct {
// A set of components known to be stable (not cause an issue by themselves) in the current search context.
StableSet sets.Set
// Mods currently being searched within for this specific bisection step.
// It is the union of C_1 and C_2.
Candidates []string
}
SearchStep represents a single logical step (or frame) in the iterative implementation of the `FindNextConflictElement` bisection algorithm. Each step contains the local context (StableSet and Candidates) relevant to that specific recursive call, pushed onto the SearchState's SearchStack.
type TestResult ¶
type TestResult string
TestResult indicates the outcome of a test run.
const ( // TestResultFail indicates the test exhibited the undesirable outcome. TestResultFail TestResult = "FAIL" // TestResultGood indicates the test ran successfully without the undesirable outcome. TestResultGood TestResult = "GOOD" // This is the initial value TestResultUndefined TestResult = "" )
type UndoFrame ¶
type UndoFrame struct {
State SearchState
Plan TestPlan
}
UndoFrame captures a complete undoable action, containing both the state before the action and the plan that was executed.
Source Files