type Caller … type logger … type Options … type Result … // Inline inlines the called function (callee) into the function call (caller) // and returns the updated, formatted content of the caller source file. // // Inline does not mutate any public fields of Caller or Callee. func Inline(caller *Caller, callee *Callee, opts *Options) (*Result, error) { … } type state … func (st *state) inline() (*Result, error) { … } type oldImport … type newImport … type inlineCallResult … // inlineCall returns a pair of an old node (the call, or something // enclosing it) and a new node (its replacement, which may be a // combination of caller, callee, and new nodes), along with the set // of new imports needed. // // TODO(adonovan): rethink the 'result' interface. The assumption of a // one-to-one replacement seems fragile. One can easily imagine the // transformation replacing the call and adding new variable // declarations, for example, or replacing a call statement by zero or // many statements.) // NOTE(rfindley): we've sort-of done this, with the 'elideBraces' flag that // allows inlining a statement list. However, due to loss of comments, more // sophisticated rewrites are challenging. // // TODO(adonovan): in earlier drafts, the transformation was expressed // by splicing substrings of the two source files because syntax // trees don't preserve comments faithfully (see #20744), but such // transformations don't compose. The current implementation is // tree-based but is very lossy wrt comments. It would make a good // candidate for evaluating an alternative fully self-contained tree // representation, such as any proposed solution to #20744, or even // dst or some private fork of go/ast.) // TODO(rfindley): see if we can reduce the amount of comment lossiness by // using printer.CommentedNode, which has been useful elsewhere. // // TODO(rfindley): inlineCall is getting very long, and very stateful, making // it very hard to read. The following refactoring may improve readability and // maintainability: // - Rename 'state' to 'callsite', since that is what it encapsulates. // - Add results of pre-processing analysis into the callsite struct, such as // the effective importMap, new/old imports, arguments, etc. Essentially // anything that resulted from initial analysis of the call site, and which // may be useful to inlining strategies. // - Delegate this call site analysis to a constructor or initializer, such // as 'analyzeCallsite', so that it does not consume bandwidth in the // 'inlineCall' logical flow. // - Once analyzeCallsite returns, the callsite is immutable, much in the // same way as the Callee and Caller are immutable. // - Decide on a standard interface for strategies (and substrategies), such // that they may be delegated to a separate method on callsite. // // In this way, the logical flow of inline call will clearly follow the // following structure: // 1. Analyze the call site. // 2. Try strategies, in order, until one succeeds. // 3. Process the results. // // If any expensive analysis may be avoided by earlier strategies, it can be // encapsulated in its own type and passed to subsequent strategies. func (st *state) inlineCall() (*inlineCallResult, error) { … } type argument … // arguments returns the effective arguments of the call. // // If the receiver argument and parameter have // different pointerness, make the "&" or "*" explicit. // // Also, if x.f() is shorthand for promoted method x.y.f(), // make the .y explicit in T.f(x.y, ...). // // Beware that: // // - a method can only be called through a selection, but only // the first of these two forms needs special treatment: // // expr.f(args) -> ([&*]expr, args) MethodVal // T.f(recv, args) -> ( expr, args) MethodExpr // // - the presence of a value in receiver-position in the call // is a property of the caller, not the callee. A method // (calleeDecl.Recv != nil) may be called like an ordinary // function. // // - the types.Signatures seen by the caller (from // StaticCallee) and by the callee (from decl type) // differ in this case. // // In a spread call f(g()), the sole ordinary argument g(), // always last in args, has a tuple type. // // We compute type-based predicates like pure, duplicable, // freevars, etc, now, before we start modifying syntax. func (st *state) arguments(caller *Caller, calleeDecl *ast.FuncDecl, assign1 func(*types.Var) bool) ([]*argument, error) { … } type parameter … type replacer … // substitute implements parameter elimination by substitution. // // It considers each parameter and its corresponding argument in turn // and evaluate these conditions: // // - the parameter is neither address-taken nor assigned; // - the argument is pure; // - if the parameter refcount is zero, the argument must // not contain the last use of a local var; // - if the parameter refcount is > 1, the argument must be duplicable; // - the argument (or types.Default(argument) if it's untyped) has // the same type as the parameter. // // If all conditions are met then the parameter can be substituted and // each reference to it replaced by the argument. In that case, the // replaceCalleeID function is called for each reference to the // parameter, and is provided with its relative offset and replacement // expression (argument), and the corresponding elements of params and // args are replaced by nil. func substitute(logf logger, caller *Caller, params []*parameter, args []*argument, effects []int, falcon falconResult, replace replacer) { … } // isConversion reports whether the given call is a type conversion, returning // (operand, true) if so. // // If the call is not a conversion, it returns (nil, false). func isConversion(info *types.Info, call *ast.CallExpr) (types.Type, bool) { … } // isNonTypeParamInterface reports whether t is a non-type parameter interface // type. func isNonTypeParamInterface(t types.Type) bool { … } // isUsedOutsideCall reports whether v is used outside of caller.Call, within // the body of caller.enclosingFunc. func isUsedOutsideCall(caller *Caller, v *types.Var) bool { … } // checkFalconConstraints checks whether constant arguments // are safe to substitute (e.g. s[i] -> ""[0] is not safe.) // // Any failed constraint causes us to reject all constant arguments as // substitution candidates (by clearing args[i].substitution=false). // // TODO(adonovan): we could obtain a finer result rejecting only the // freevars of each failed constraint, and processing constraints in // order of increasing arity, but failures are quite rare. func checkFalconConstraints(logf logger, params []*parameter, args []*argument, falcon falconResult) { … } // resolveEffects marks arguments as non-substitutable to resolve // hazards resulting from the callee evaluation order described by the // effects list. // // To do this, each argument is categorized as a read (R), write (W), // or pure. A hazard occurs when the order of evaluation of a W // changes with respect to any R or W. Pure arguments can be // effectively ignored, as they can be safely evaluated in any order. // // The callee effects list contains the index of each parameter in the // order it is first evaluated during execution of the callee. In // addition, the two special values R∞ and W∞ indicate the relative // position of the callee's first non-parameter read and its first // effects (or other unknown behavior). // For example, the list [0 2 1 R∞ 3 W∞] for func(a, b, c, d) // indicates that the callee referenced parameters a, c, and b, // followed by an arbitrary read, then parameter d, and finally // unknown behavior. // // When an argument is marked as not substitutable, we say that it is // 'bound', in the sense that its evaluation occurs in a binding decl // or literalized call. Such bindings always occur in the original // callee parameter order. // // In this context, "resolving hazards" means binding arguments so // that they are evaluated in a valid, hazard-free order. A trivial // solution to this problem would be to bind all arguments, but of // course that's not useful. The goal is to bind as few arguments as // possible. // // The algorithm proceeds by inspecting arguments in reverse parameter // order (right to left), preserving the invariant that every // higher-ordered argument is either already substituted or does not // need to be substituted. At each iteration, if there is an // evaluation hazard in the callee effects relative to the current // argument, the argument must be bound. Subsequently, if the argument // is bound for any reason, each lower-ordered argument must also be // bound if either the argument or lower-order argument is a // W---otherwise the binding itself would introduce a hazard. // // Thus, after each iteration, there are no hazards relative to the // current argument. Subsequent iterations cannot introduce hazards // with that argument because they can result only in additional // binding of lower-ordered arguments. func resolveEffects(logf logger, args []*argument, effects []int) { … } // updateCalleeParams updates the calleeDecl syntax to remove // substituted parameters and move the receiver (if any) to the head // of the ordinary parameters. func updateCalleeParams(calleeDecl *ast.FuncDecl, params []*parameter) { … } type bindingDeclInfo … // createBindingDecl constructs a "binding decl" that implements // parameter assignment and declares any named result variables // referenced by the callee. It returns nil if there were no // unsubstituted parameters. // // It may not always be possible to create the decl (e.g. due to // shadowing), in which case it also returns nil; but if it succeeds, // the declaration may be used by reduction strategies to relax the // requirement that all parameters have been substituted. // // For example, a call: // // f(a0, a1, a2) // // where: // // func f(p0, p1 T0, p2 T1) { body } // // reduces to: // // { // var ( // p0, p1 T0 = a0, a1 // p2 T1 = a2 // ) // body // } // // so long as p0, p1 ∉ freevars(T1) or freevars(a2), and so on, // because each spec is statically resolved in sequence and // dynamically assigned in sequence. By contrast, all // parameters are resolved simultaneously and assigned // simultaneously. // // The pX names should already be blank ("_") if the parameter // is unreferenced; this avoids "unreferenced local var" checks. // // Strategies may impose additional checks on return // conversions, labels, defer, etc. func createBindingDecl(logf logger, caller *Caller, args []*argument, calleeDecl *ast.FuncDecl, results []*paramInfo) *bindingDeclInfo { … } // lookup does a symbol lookup in the lexical environment of the caller. func (caller *Caller) lookup(name string) types.Object { … } func scopeFor(info *types.Info, n ast.Node) *types.Scope { … } // freeVars returns the names of all free identifiers of e: // those lexically referenced by it but not defined within it. // (Fields and methods are not included.) func freeVars(info *types.Info, e ast.Expr) map[string]bool { … } // freeishNames computes an over-approximation to the free names // of the type syntax t, inserting values into the map. // // Because we don't have go/types annotations, we can't give an exact // result in all cases. In particular, an array type [n]T might have a // size such as unsafe.Sizeof(func() int{stmts...}()) and now the // precise answer depends upon all the statement syntax too. But that // never happens in practice. func freeishNames(free map[string]bool, t ast.Expr) { … } // effects reports whether an expression might change the state of the // program (through function calls and channel receives) and affect // the evaluation of subsequent expressions. func (st *state) effects(info *types.Info, expr ast.Expr) bool { … } // pure reports whether an expression has the same result no matter // when it is executed relative to other expressions, so it can be // commuted with any other expression or statement without changing // its meaning. // // An expression is considered impure if it reads the contents of any // variable, with the exception of "single assignment" local variables // (as classified by the provided callback), which are never updated // after their initialization. // // Pure does not imply duplicable: for example, new(T) and T{} are // pure expressions but both return a different value each time they // are evaluated, so they are not safe to duplicate. // // Purity does not imply freedom from run-time panics. We assume that // target programs do not encounter run-time panics nor depend on them // for correct operation. // // TODO(adonovan): add unit tests of this function. func pure(info *types.Info, assign1 func(*types.Var) bool, e ast.Expr) bool { … } // callsPureBuiltin reports whether call is a call of a built-in // function that is a pure computation over its operands (analogous to // a + operator). Because it does not depend on program state, it may // be evaluated at any point--though not necessarily at multiple // points (consider new, make). func callsPureBuiltin(info *types.Info, call *ast.CallExpr) bool { … } // duplicable reports whether it is appropriate for the expression to // be freely duplicated. // // Given the declaration // // func f(x T) T { return x + g() + x } // // an argument y is considered duplicable if we would wish to see a // call f(y) simplified to y+g()+y. This is true for identifiers, // integer literals, unary negation, and selectors x.f where x is not // a pointer. But we would not wish to duplicate expressions that: // - have side effects (e.g. nearly all calls), // - are not referentially transparent (e.g. &T{}, ptr.field, *ptr), or // - are long (e.g. "huge string literal"). func duplicable(info *types.Info, e ast.Expr) bool { … } func consteq(x, y constant.Value) bool { … } var kZeroInt … var kZeroString … var kZeroFloat … var kOneFloat … func assert(cond bool, msg string) { … } // blanks returns a slice of n > 0 blank identifiers. func blanks[E ast.Expr](n int) []E { … } func makeIdent(name string) *ast.Ident { … } // importedPkgName returns the PkgName object declared by an ImportSpec. // TODO(adonovan): make this a method of types.Info (#62037). func importedPkgName(info *types.Info, imp *ast.ImportSpec) (*types.PkgName, bool) { … } func isPkgLevel(obj types.Object) bool { … } // callContext returns the two nodes immediately enclosing the call // (specified as a PathEnclosingInterval), ignoring parens. func callContext(callPath []ast.Node) (parent, grandparent ast.Node) { … } // hasLabelConflict reports whether the set of labels of the function // enclosing the call (specified as a PathEnclosingInterval) // intersects with the set of callee labels. func hasLabelConflict(callPath []ast.Node, calleeLabels []string) bool { … } // callerLabels returns the set of control labels in the function (if // any) enclosing the call (specified as a PathEnclosingInterval). func callerLabels(callPath []ast.Node) map[string]bool { … } // callerFunc returns the innermost Func{Decl,Lit} node enclosing the // call (specified as a PathEnclosingInterval). func callerFunc(callPath []ast.Node) ast.Node { … } // callStmt reports whether the function call (specified // as a PathEnclosingInterval) appears within an ExprStmt, // and returns it if so. // // If unrestricted, callStmt returns nil if the ExprStmt f() appears // in a restricted context (such as "if f(); cond {") where it cannot // be replaced by an arbitrary statement. (See "statement theory".) func callStmt(callPath []ast.Node, unrestricted bool) *ast.ExprStmt { … } // replaceNode performs a destructive update of the tree rooted at // root, replacing each occurrence of "from" with "to". If to is nil and // the element is within a slice, the slice element is removed. // // The root itself cannot be replaced; an attempt will panic. // // This function must not be called on the caller's syntax tree. // // TODO(adonovan): polish this up and move it to astutil package. // TODO(adonovan): needs a unit test. func replaceNode(root ast.Node, from, to ast.Node) { … } // clearPositions destroys token.Pos information within the tree rooted at root, // as positions in callee trees may cause caller comments to be emitted prematurely. // // In general it isn't safe to clear a valid Pos because some of them // (e.g. CallExpr.Ellipsis, TypeSpec.Assign) are significant to // go/printer, so this function sets each non-zero Pos to 1, which // suffices to avoid advancing the printer's comment cursor. // // This function mutates its argument; do not invoke on caller syntax. // // TODO(adonovan): remove this horrendous workaround when #20744 is finally fixed. func clearPositions(root ast.Node) { … } // findIdent finds the Ident beneath root that has the given pos. // It returns the path to the ident (excluding the ident), and the ident // itself, where the path is the sequence of ast.Nodes encountered in a // depth-first search to find ident. func findIdent(root ast.Node, pos token.Pos) ([]ast.Node, *ast.Ident) { … } func prepend[T any](elem T, slice ...T) []T { … } // debugFormatNode formats a node or returns a formatting error. // Its sloppy treatment of errors is appropriate only for logging. func debugFormatNode(fset *token.FileSet, n ast.Node) string { … } func shallowCopy[T any](ptr *T) *T { … } // ∀ func forall[T any](list []T, f func(i int, x T) bool) bool { … } // ∃ func exists[T any](list []T, f func(i int, x T) bool) bool { … } // last returns the last element of a slice, or zero if empty. func last[T any](slice []T) T { … } // canImport reports whether one package is allowed to import another. // // TODO(adonovan): allow customization of the accessibility relation // (e.g. for Bazel). func canImport(from, to string) bool { … } // consistentOffsets reports whether the portion of caller.Content // that corresponds to caller.Call can be parsed as a call expression. // If not, the client has provided inconsistent information, possibly // because they forgot to ignore line directives when computing the // filename enclosing the call. // This is just a heuristic. func consistentOffsets(caller *Caller) bool { … } // needsParens reports whether parens are required to avoid ambiguity // around the new node replacing the specified old node (which is some // ancestor of the CallExpr identified by its PathEnclosingInterval). func needsParens(callPath []ast.Node, old, new ast.Node) bool { … } // declares returns the set of lexical names declared by a // sequence of statements from the same block, excluding sub-blocks. // (Lexical names do not include control labels.) func declares(stmts []ast.Stmt) map[string]bool { … } type importNameFunc … // assignStmts rewrites a statement assigning the results of a call into zero // or more statements that assign its return operands, or (nil, false) if no // such rewrite is possible. The set of bindings created by the result of // assignStmts is the same as the set of bindings created by the callerStmt. // // The callee must contain exactly one return statement. // // This is (once again) a surprisingly complex task. For example, depending on // types and existing bindings, the assignment // // a, b := f() // // could be rewritten as: // // a, b := 1, 2 // // but may need to be written as: // // a, b := int8(1), int32(2) // // In the case where the return statement within f is a spread call to another // function g(), we cannot explicitly convert the return values inline, and so // it may be necessary to split the declaration and assignment of variables // into separate statements: // // a, b := g() // // or // // var a int32 // a, b = g() // // or // // var ( // a int8 // b int32 // ) // a, b = g() // // Note: assignStmts may return (nil, true) if it determines that the rewritten // assignment consists only of _ = nil assignments. func (st *state) assignStmts(callerStmt *ast.AssignStmt, returnOperands []ast.Expr, importName importNameFunc) ([]ast.Stmt, bool) { … } // tailCallSafeReturn reports whether the callee's return statements may be safely // used to return from the function enclosing the caller (which must exist). func tailCallSafeReturn(caller *Caller, calleeSymbol *types.Func, callee *gobCallee) bool { … } // hasNonTrivialReturn reports whether any of the returns involve a nontrivial // implicit conversion of a result expression. func hasNonTrivialReturn(returnInfo [][]returnOperandFlags) bool { … } // soleUse returns the ident that refers to obj, if there is exactly one. func soleUse(info *types.Info, obj types.Object) (sole *ast.Ident) { … } type unit … // slicesDeleteFunc removes any elements from s for which del returns true, // returning the modified slice. // slicesDeleteFunc zeroes the elements between the new length and the original length. // TODO(adonovan): use go1.21 slices.DeleteFunc func slicesDeleteFunc[S ~[]E, E any](s S, del func(E) bool) S { … } // slicesIndexFunc returns the first index i satisfying f(s[i]), // or -1 if none do. func slicesIndexFunc[S ~[]E, E any](s S, f func(E) bool) int { … }
Codebase Browser
gotools