16 void addBuiltin(std::string Name) {
21 [[nodiscard(
"Record ToDef Map!")]] std::shared_ptr<Definition>
22 add(std::string Name,
const Node *Entry,
24 assert(!Def.contains(Name));
25 auto NewDef = std::make_shared<Definition>(Entry, Source);
26 Def.insert({std::move(Name), NewDef});
36 for (
const auto &[_, D] : Defs) {
37 if (!D->uses().empty())
43void VariableLookupAnalysis::emitEnvLivenessWarning(
44 const std::shared_ptr<EnvNode> &NewEnv) {
45 for (
const auto &[Name, Def] : NewEnv->defs()) {
54 if (Def->uses().empty()) {
55 Diagnostic::DiagnosticKind Kind = [&]() {
56 switch (Def->source()) {
58 return Diagnostic::DK_UnusedDefLet;
60 return Diagnostic::DK_UnusedDefLambdaNoArg_Formal;
62 return Diagnostic::DK_UnusedDefLambdaWithArg_Formal;
64 return Diagnostic::DK_UnusedDefLambdaWithArg_Arg;
66 assert(
false &&
"liveness diagnostic encountered an unknown source!");
67 __builtin_unreachable();
70 Diagnostic &D = Diags.emplace_back(Kind, Def->syntax()->range());
77void VariableLookupAnalysis::lookupVar(
const ExprVar &Var,
78 const std::shared_ptr<EnvNode> &Env) {
79 const std::string &Name = Var.
id().
name();
81 bool EnclosedWith =
false;
84 std::shared_ptr<Definition> Def;
85 for (; CurEnv; CurEnv = CurEnv->
parent()) {
86 if (CurEnv->
defs().contains(Name)) {
87 Def = CurEnv->
defs().at(Name);
91 if (CurEnv->
isWith() && !EnclosedWith) {
103 Def = WithDefs.at(WithEnv->
syntax());
112 Diags.emplace_back(Diagnostic::DK_UndefinedVariable, Var.
range());
116void VariableLookupAnalysis::dfs(
const ExprLambda &Lambda,
117 const std::shared_ptr<EnvNode> &Env) {
124 assert(Lambda.
arg());
131 ToDef.insert_or_assign(Arg.
id(), DBuilder.add(Arg.
id()->
name(), Arg.
id(),
136 ToDef.insert_or_assign(Arg.
id(),
137 DBuilder.add(Arg.
id()->
name(), Arg.
id(),
154 for (
const auto &[Name,
Formal] : Arg.formals()->dedup()) {
158 ToDef.insert_or_assign(
Formal->
id(),
159 DBuilder.add(Name,
Formal->
id(), Source));
163 auto NewEnv = std::make_shared<EnvNode>(Env, DBuilder.finish(), &Lambda);
166 for (
const auto &
Formal : Arg.formals()->members()) {
173 dfs(*Lambda.
body(), NewEnv);
175 emitEnvLivenessWarning(NewEnv);
178void VariableLookupAnalysis::dfsDynamicAttrs(
179 const std::vector<Attribute> &DynamicAttrs,
180 const std::shared_ptr<EnvNode> &Env) {
181 for (
const auto &Attr : DynamicAttrs) {
184 dfs(Attr.key(), Env);
185 dfs(*Attr.value(), Env);
189std::shared_ptr<EnvNode> VariableLookupAnalysis::dfsAttrs(
190 const SemaAttrs &SA,
const std::shared_ptr<EnvNode> &Env,
196 for (
const auto &[Name, Attr] : SA.staticAttrs())
197 ToDef.insert_or_assign(&Attr.key(), DB.add(Name, &Attr.key(), Source));
199 auto NewEnv = std::make_shared<EnvNode>(Env, DB.finish(), Syntax);
201 for (
const auto &[_, Attr] : SA.staticAttrs()) {
206 dfs(*Attr.value(), NewEnv);
209 dfs(*Attr.value(), Env);
218 for (
const auto &[_, Attr] : SA.staticAttrs()) {
221 dfs(*Attr.value(), Env);
228void VariableLookupAnalysis::dfs(
const ExprAttrs &Attrs,
229 const std::shared_ptr<EnvNode> &Env) {
231 std::shared_ptr<EnvNode> NewEnv =
235 "NewEnv must be created for recursive attrset");
236 if (!NewEnv->isLive()) {
237 Diagnostic &D = Diags.emplace_back(Diagnostic::DK_ExtraRecursive,
239 D.
fix(
"remove `rec` keyword")
246void VariableLookupAnalysis::dfs(
const ExprLet &Let,
247 const std::shared_ptr<EnvNode> &Env) {
250 auto GetLetEnv = [&Env, &Let,
this]() -> std::shared_ptr<EnvNode> {
259 assert(SA.
isRecursive() &&
"let ... in ... attrset must be recursive");
263 auto LetEnv = GetLetEnv();
266 dfs(*Let.
expr(), LetEnv);
267 emitEnvLivenessWarning(LetEnv);
270void VariableLookupAnalysis::trivialDispatch(
271 const Node &Root,
const std::shared_ptr<EnvNode> &Env) {
272 for (
const Node *Ch : Root.children()) {
279void VariableLookupAnalysis::dfs(
const ExprWith &With,
280 const std::shared_ptr<EnvNode> &Env) {
281 auto NewEnv = std::make_shared<EnvNode>(Env,
EnvNode::DefMap{}, &With);
282 if (!WithDefs.contains(&With)) {
285 ToDef.insert_or_assign(&With.
kwWith(), NewDef);
286 WithDefs.insert_or_assign(&With, NewDef);
290 dfs(*With.
with(), Env);
293 dfs(*With.
expr(), NewEnv);
295 if (WithDefs.at(&With)->uses().empty()) {
297 Diags.emplace_back(Diagnostic::DK_ExtraWith, With.
kwWith().
range());
298 Fix &F = D.
fix(
"remove `with` expression")
307void VariableLookupAnalysis::dfs(
const Node &Root,
308 const std::shared_ptr<EnvNode> &Env) {
309 Envs.insert({&Root, Env});
310 switch (Root.
kind()) {
311 case Node::NK_ExprVar: {
312 const auto &Var =
static_cast<const ExprVar &
>(Root);
316 case Node::NK_ExprLambda: {
317 const auto &Lambda =
static_cast<const ExprLambda &
>(Root);
321 case Node::NK_ExprAttrs: {
322 const auto &Attrs =
static_cast<const ExprAttrs &
>(Root);
326 case Node::NK_ExprLet: {
327 const auto &Let =
static_cast<const ExprLet &
>(Root);
331 case Node::NK_ExprWith: {
332 const auto &With =
static_cast<const ExprWith &
>(Root);
337 trivialDispatch(Root, Env);
344 std::vector<std::string> Builtins{
350 "__addDrvOutputDependencies",
366 "__flakeRefToString",
425 "__concatStringsSep",
438 "__unsafeDiscardOutputDependency",
443 "__unsafeDiscardStringContext",
448 "__unsafeGetAttrPos",
464 for (
const auto &Builtin : Builtins)
465 DB.addBuiltin(Builtin);
467 auto Env = std::make_shared<EnvNode>(
nullptr, DB.finish(),
nullptr);
476 if (!Envs.contains(N))
478 return Envs.at(N).get();
Lookup variable names, from it's parent scope.
@ InheritFrom
inherit (expr) a b c
DefinitionSource
"Source" information so we can know where the def comes from.
@ DS_Rec
From recursive attribute set. e.g. rec { }.
@ DS_LambdaArg
From ambda arg e.g. a: a + 1.
@ DS_LambdaNoArg_Formal
From lambda (noarg) formal, e.g. { a }: a + 1.
@ DS_Builtin
Builtin names.
@ DS_LambdaWithArg_Arg
From lambda (with @arg) arg, e.g. a in { foo }@a: foo + 1
@ DS_With
From with <expr>;.
@ DS_LambdaWithArg_Formal
From lambda (with @arg) formal, e.g. foo in { foo }@a: foo + 1
@ DS_Let
From let ... in ...
Fix & fix(std::string Message)
A set of variable definitions, which may inherit parent environment.
const Node * syntax() const
Where this node comes from.
std::map< std::string, std::shared_ptr< Definition > > DefMap
const DefMap & defs() const
const SemaAttrs & sema() const
const ExprAttrs * attrs() const
const Expr * expr() const
const Identifier & id() const
const Misc & kwWith() const
const Misc * tokSemi() const
Fix & edit(TextEdit Edit)
const std::string & name() const
Formals * formals() const
LexerCursorRange range() const
void tag(DiagnosticTag Tag)
Attribute set after deduplication.
bool isRecursive() const
If the attribute set is rec.
const std::vector< Attribute > & dynamicAttrs() const
Dynamic attributes, require evaluation to get the key.
static TextEdit mkRemoval(LexerCursorRange RemovingRange)
const EnvNode * env(const Node *N) const
void runOnAST(const Node &Root)
Perform variable lookup analysis (def-use) on AST.
VariableLookupAnalysis(std::vector< Diagnostic > &Diags)