Documentation
¶
Overview ¶
key.go provides path key construction and manipulation utilities.
Path keys are the canonical string identifiers for versioned paths in the flow solver. This file provides functions for building, parsing, and comparing path keys.
Package pathkey provides canonical path key generation for flow analysis.
In SSA form, each variable has multiple versions at different program points. This package maps constraint paths (symbol + field segments) to canonical versioned keys that uniquely identify the variable incarnation.
Key format: sym<SymbolID>@<VersionID><segments> Example: sym42@3.field[0] refers to symbol 42, version 3, field "field", index 0.
util.go provides parsing utilities for path key construction.
These functions handle low-level parsing of identifiers and numbers in path syntax, enabling path key parsing and construction.
Index ¶
- Constants
- func CollectEquivalentPaths(constraints []constraint.Constraint, target constraint.Path) map[constraint.PathKey]bool
- func FilterConstraintsForPath(constraints []constraint.Constraint, target constraint.Path) []constraint.Constraint
- func FloatToSafeInt(f float64) (int, bool)
- func IntToString(v int) string
- func IsIdentName(s string) bool
- func IsIdentPart(ch byte) bool
- func IsIdentStart(ch byte) bool
- func KeySymbol(key constraint.PathKey) cfg.SymbolID
- func KeysShareSymbol(a, b constraint.PathKey) bool
- func ParseIntLiteral(s string) (int, bool)
- func ParseKey(key constraint.PathKey) (cfg.SymbolID, int, string, bool)
- func ParseRootAndSuffix(key constraint.PathKey) (root string, suffix string, ok bool)
- func ParseSuffix(suffix string) []constraint.Segment
- func PathRelated(target constraint.Path, other constraint.Path) bool
- func ReadIdent(s string, idx *int) string
- func SegmentsPrefix(a, b []constraint.Segment) bool
- func SegmentsSuffix(segs []constraint.Segment) string
- func SymbolRoot(sym cfg.SymbolID) string
- func SymbolVersionRoot(sym cfg.SymbolID, versionID int) string
- type Resolver
- func (r *Resolver) HasVersion(p cfg.Point, path constraint.Path) bool
- func (r *Resolver) KeyAt(p cfg.Point, path constraint.Path) constraint.PathKey
- func (r *Resolver) KeyAtVersion(sym cfg.SymbolID, versionID int, segments []constraint.Segment) constraint.PathKey
- func (r *Resolver) VersionAtSym(p cfg.Point, sym cfg.SymbolID) cfg.Version
- type VersionedGraph
Constants ¶
const MaxSafeFloat64Int = (1 << 53) - 1
MaxSafeFloat64Int is the largest integer magnitude that can be exactly represented in float64.
IEEE 754 double precision has a 53-bit significand, so integers up to 2^53 - 1 can be represented exactly. Beyond this, consecutive integers may round to the same float64 value, causing precision loss.
This constant is used to validate integer conversions from Lua numbers, which are all represented as float64 internally.
Variables ¶
This section is empty.
Functions ¶
func CollectEquivalentPaths ¶
func CollectEquivalentPaths(constraints []constraint.Constraint, target constraint.Path) map[constraint.PathKey]bool
CollectEquivalentPaths finds all paths equivalent to target via equality constraints.
Equivalence is transitive: if x == y and y == z, then x, y, and z are all equivalent. The function uses a fixed-point algorithm to compute the full equivalence closure.
Supported constraint types for equivalence:
- EqPath: x == y means x and y are equivalent
- FieldEqualsPath: x.field == y means x.field and y are equivalent
- IndexEqualsPath: x[i] == y means x[i] and y are equivalent
Returns a set of PathKeys that are transitively equivalent to target.
func FilterConstraintsForPath ¶
func FilterConstraintsForPath(constraints []constraint.Constraint, target constraint.Path) []constraint.Constraint
FilterConstraintsForPath returns constraints relevant to a target path.
A constraint is kept if it references the target path or an equivalent path (via EqPath constraints). This filtering is used before applying constraints to narrow a specific path, avoiding application of unrelated constraints.
The function handles several cases:
- Direct reference: Constraint path related to target
- Equivalence: Constraint path equivalent to target via EqPath
- Field/Index relationships: Value paths from FieldEqualsPath constraints
Special handling for NotEquals constraints: They narrow the target, not the value side. If filtering for a value-only path, NotEquals are dropped.
func FloatToSafeInt ¶
FloatToSafeInt converts a float64 to int if it represents a whole number safely.
Returns (value, true) if:
- The float has no fractional part (float64(int64(f)) == f)
- The magnitude is within MaxSafeFloat64Int
Returns (0, false) if the conversion would lose precision or the value is not an exact integer. This is used for array index validation where only exact integers are valid indices.
func IntToString ¶
IntToString converts an integer to its string representation.
This is a simple implementation without strconv for hot paths.
func IsIdentName ¶
IsIdentName reports whether s is a valid Lua identifier name.
A valid identifier is non-empty, starts with IsIdentStart, and all subsequent characters satisfy IsIdentPart. This validates variable names, field names, etc.
func IsIdentPart ¶
IsIdentPart reports whether ch can appear in a Lua identifier (after the first character).
In Lua, identifiers can contain letters, digits (0-9), and underscores. The first character must satisfy IsIdentStart; subsequent characters satisfy IsIdentPart.
func IsIdentStart ¶
IsIdentStart reports whether ch can start a Lua identifier.
In Lua, identifiers must start with a letter (A-Z, a-z) or underscore (_). This matches Lua's lexical rules for variable names.
func KeySymbol ¶
func KeySymbol(key constraint.PathKey) cfg.SymbolID
KeySymbol extracts the symbol ID from a canonical key.
This is a convenience wrapper around ParseKey for when only the symbol is needed. Returns 0 if the key is not a valid canonical key.
func KeysShareSymbol ¶
func KeysShareSymbol(a, b constraint.PathKey) bool
KeysShareSymbol returns true if both keys reference the same symbol.
This is used to check if two keys are versions of the same variable, regardless of version number or path suffix. Useful for phi node handling and constraint propagation across versions.
func ParseIntLiteral ¶
ParseIntLiteral parses a string as a non-negative integer literal.
Returns the integer value and true if the string contains only ASCII digits. Returns (0, false) for empty strings, negative numbers, or non-digit characters.
This is used to distinguish integer indices ([0], [1]) from string indices ([key]) in path suffix parsing.
func ParseKey ¶
ParseKey extracts components from a canonical key string.
This is the inverse of buildKey. Given "sym42@3.field", returns:
- SymbolID: 42
- VersionID: 3
- Suffix: ".field"
- OK: true
For keys without a version (missing @), versionID is 0. For keys that don't start with "sym", returns (0, 0, "", false).
The suffix includes any field or index path after the version number.
func ParseRootAndSuffix ¶ added in v1.5.6
func ParseRootAndSuffix(key constraint.PathKey) (root string, suffix string, ok bool)
ParseRootAndSuffix splits a key into its canonical root and suffix.
Canonical roots are:
- Symbol keys: sym<ID> or sym<ID>@<version>
- Placeholder roots: $<index>
- Return roots: ret[<index>]
For legacy keys that don't match the canonical forms, the function falls back to splitting at the first '.' or '[' and returns that prefix as root.
func ParseSuffix ¶
func ParseSuffix(suffix string) []constraint.Segment
ParseSuffix converts a suffix string like ".field" or "[0]" to segments.
This is the inverse of SegmentsSuffix. It parses path suffixes extracted from canonical keys back into structured segments.
Supported syntax:
- ".field" -> SegmentField{Name: "field"}
- "[0]" -> SegmentIndexInt{Index: 0}
- "[\"key\"]" -> SegmentIndexString{Name: "key"}
- "[key]" -> SegmentIndexString{Name: "key"} (legacy form)
The parser handles multiple chained segments: ".foo[0].bar" produces [SegmentField{foo}, SegmentIndexInt{0}, SegmentField{bar}].
func PathRelated ¶
func PathRelated(target constraint.Path, other constraint.Path) bool
PathRelated returns true if target and other paths share identity and overlap.
Two paths are related if:
- They share the same symbol (SSA identity) or both are placeholders with the same Root name
- One is a prefix of the other (including equality)
This relationship is used for constraint filtering: a constraint on x.foo is related to path x (constraint might narrow x) and to path x.foo.bar (constraint directly applies).
Strictly requires symbol matching - no name-based fallback. If one path has a symbol and the other doesn't, they are not related. This prevents unsound constraint propagation across different scopes.
Version mismatches do not block relation checks. Versioned staleness is handled by assignment-driven condition killing, while relation itself must stay stable across SSA versions so unaffected constraints (for sibling/root paths) survive field-only redefinitions.
func ReadIdent ¶
ReadIdent reads a Lua identifier from s starting at *idx, advancing *idx past it.
An identifier starts with IsIdentStart and continues with IsIdentPart characters. The function modifies *idx in place to point past the consumed identifier.
Returns the identifier string, or empty string if no valid identifier starts at *idx. If idx is nil or out of bounds, returns empty string without modifying idx.
func SegmentsPrefix ¶
func SegmentsPrefix(a, b []constraint.Segment) bool
SegmentsPrefix returns true if a is a prefix of b (or equal).
Segment comparison is exact: both kind and value must match. An empty slice is a prefix of any slice.
func SegmentsSuffix ¶
func SegmentsSuffix(segs []constraint.Segment) string
SegmentsSuffix converts path segments to a suffix string for key construction.
The suffix format matches Lua syntax:
- Field segments: ".field"
- Integer index: "[0]"
- String index: "[\"key\"]" (with escaping)
This is a thin wrapper around constraint.FormatSegments for API consistency within the pathkey package.
func SymbolRoot ¶ added in v1.5.6
SymbolRoot returns the canonical symbol root "sym<id>".
Types ¶
type Resolver ¶
type Resolver struct {
// contains filtered or unexported fields
}
Resolver provides canonical path key generation from constraint paths.
All path-to-key conversions in the flow solver must go through the resolver to ensure consistent SSA versioning. The resolver encapsulates the logic for:
- Querying the CFG for visible SSA versions
- Building canonical key strings in the "sym<ID>@<Ver><segments>" format
- Handling placeholder paths (used in function effects)
- Validating that paths have resolvable versions
Using the resolver ensures that the same path at the same point always produces the same key, enabling correct value lookup and constraint matching.
func NewResolver ¶
func NewResolver(g VersionedGraph) *Resolver
NewResolver creates a resolver bound to a versioned graph.
The graph must provide SSA version lookup for all symbols that will be resolved. Typically this is a cfg.VersionedGraph from CFG construction.
func (*Resolver) HasVersion ¶
HasVersion returns true if a valid SSA version exists for the path at point p.
A path has a version if:
- It is not empty
- It is not a placeholder ($0, $1, etc.)
- It has a Symbol
- The symbol has a non-zero version at point p
This is used to check if a path can be resolved before attempting resolution.
func (*Resolver) KeyAt ¶
func (r *Resolver) KeyAt(p cfg.Point, path constraint.Path) constraint.PathKey
KeyAt returns the canonical key for a path at a CFG point. This is the ONLY method that should be used for path→key conversion.
Canonical key format: sym<SymbolID>@<VersionID><segments> Example: sym42@3.field[0]
Rules:
- Symbol=0 paths (placeholders) use Root as-is
- Requires valid SSA version for non-placeholder paths
- Returns empty string if path is empty or version unavailable
func (*Resolver) KeyAtVersion ¶
func (r *Resolver) KeyAtVersion(sym cfg.SymbolID, versionID int, segments []constraint.Segment) constraint.PathKey
KeyAtVersion returns the canonical key using an explicit version ID. Use when version is already known (e.g., from phi operands).
func (*Resolver) VersionAtSym ¶
VersionAtSym returns the visible SSA version for a symbol at point p.
This is a convenience method when you have a SymbolID rather than a full Path. Equivalent to calling VersionAt with Path{Symbol: sym}.
type VersionedGraph ¶
type VersionedGraph interface {
// VisibleVersion returns the SSA version of sym that is visible at point p.
// Returns a zero Version if no version is visible (symbol not in scope).
VisibleVersion(p cfg.Point, sym cfg.SymbolID) cfg.Version
}
VersionedGraph provides SSA version lookup for symbols at CFG points.
In SSA form, each variable has multiple versions corresponding to different assignments. VisibleVersion returns the version of a symbol that is "live" at a particular program point - the most recent assignment that dominates the point.
Source Files