aboutsummaryrefslogtreecommitdiff
path: root/libbuild2/dyndep.cxx
blob: 5ac9648b2ac83f675d7ee8c43f4960e2c0d95a51 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
// file      : libbuild2/dyndep.cxx -*- C++ -*-
// license   : MIT; see accompanying LICENSE file

#include <libbuild2/dyndep.hxx>

#include <libbuild2/scope.hxx>
#include <libbuild2/target.hxx>
#include <libbuild2/context.hxx>
#include <libbuild2/algorithm.hxx>
#include <libbuild2/filesystem.hxx>
#include <libbuild2/diagnostics.hxx>

using namespace std;
using namespace butl;

namespace build2
{
  bool dyndep_rule::
  update (tracer& trace, action a, const target& t, timestamp ts)
  {
    return update_during_match (trace, a, t, ts);
  }

  optional<bool> dyndep_rule::
  inject_file (tracer& trace, const char* what,
               action a, target& t,
               const file& pt,
               timestamp mt,
               bool f,
               bool adhoc,
               uintptr_t data)
  {
    // Even if failing we still use try_match_sync() in order to issue
    // consistent (with other places) diagnostics (rather than the generic
    // "not rule to update ...").
    //
    if (!try_match_sync (a, pt).first)
    {
      if (!f)
        return nullopt;

      diag_record dr;
      dr << fail << what << ' ' << pt << " not found and no rule to "
         << "generate it";

      if (verb < 4)
        dr << info << "re-run with --verbose=4 for more information";
    }

    bool r (update (trace, a, pt, mt));

    // Add to our prerequisite target list.
    //
    t.prerequisite_targets[a].emplace_back (&pt, adhoc, data);

    return r;
  }

  // Check if the specified prerequisite is updated during match by any other
  // prerequisites of the specified target, recursively.
  //
  static bool
  updated_during_match (action a, const target& t, size_t pts_n,
                        const target& pt)
  {
    const auto& pts (t.prerequisite_targets[a]);

    for (size_t i (0); i != pts_n; ++i)
    {
      const prerequisite_target& p (pts[i]);

      // @@ This currently doesn't cover adhoc targets if matched with
      //    buildscript (it stores them in p.data). Probably need to redo
      //    things there (see adhoc_buildscript_rule::apply()).
      //
      if (p.target != nullptr)
      {
        if (p.target == &pt &&
            (p.include & prerequisite_target::include_udm) != 0)
          return true;

        if (size_t n = p.target->prerequisite_targets[a].size ())
        {
          if (updated_during_match (a, *p.target, n, pt))
            return true;
        }
      }
    }

    return false;
  }

  optional<bool> dyndep_rule::
  inject_existing_file (tracer& trace, const char* what,
                        action a, target& t, size_t pts_n,
                        const file& pt,
                        timestamp mt,
                        bool f,
                        bool adhoc,
                        uintptr_t data)
  {
    if (!try_match_sync (a, pt).first)
    {
      if (!f)
        return nullopt;

      diag_record dr;
      dr << fail << what << ' ' << pt << " not found and no rule to "
         << "generate it";

      if (verb < 4)
        dr << info << "re-run with --verbose=4 for more information";
    }

    recipe_function* const* rf (pt[a].recipe.target<recipe_function*> ());
    if (rf == nullptr || *rf != &noop_action)
    {
      if (!updated_during_match (a, t, pts_n, pt))
      {
        fail << what << ' ' << pt << " has non-noop recipe" <<
          info << "consider listing it as static prerequisite of " << t;
      }
    }

    bool r (update (trace, a, pt, mt));

    // Add to our prerequisite target list.
    //
    t.prerequisite_targets[a].emplace_back (&pt, adhoc, data);

    return r;
  }

  void dyndep_rule::
  verify_existing_file (tracer&, const char* what,
                        action a, const target& t, size_t pts_n,
                        const file& pt)
  {
    diag_record dr;

    if (pt.matched (a))
    {
      recipe_function* const* rf (pt[a].recipe.target<recipe_function*> ());
      if (rf == nullptr || *rf != &noop_action)
      {
        if (!updated_during_match (a, t, pts_n, pt))
        {
          dr << fail << what << ' ' << pt << " has non-noop recipe";
        }
      }
    }
    else if (pt.decl == target_decl::real)
    {
      // Note that this target could not possibly be updated during match
      // since it's not matched.
      //
      dr << fail << what << ' ' << pt << " is explicitly declared as "
         << "target and may have non-noop recipe";
    }

    if (!dr.empty ())
      dr << info << "consider listing it as static prerequisite of " << t;
  }

  small_vector<const target_type*, 2> dyndep_rule::
  map_extension (const scope& bs,
                 const string& n, const string& e,
                 const target_type* const* tts)
  {
    // We will just have to try all of the possible ones, in the "most
    // likely to match" order.
    //
    auto test = [&bs, &n, &e] (const target_type& tt) -> bool
    {
      if (tt.default_extension != nullptr)
      {
        // Call the extension derivation function. Here we know that it will
        // only use the target type and name from the target key so we can
        // pass bogus values for the rest.
        //
        target_key tk {&tt, nullptr, nullptr, &n, nullopt};

        // This is like prerequisite search.
        //
        optional<string> de (tt.default_extension (tk, bs, nullptr, true));

        return de && *de == e;
      }

      return false;
    };

    small_vector<const target_type*, 2> r;

    if (tts != nullptr)
    {
      // @@ What if these types are not known by this project? Maybe this
      //    should just be unified with the below loop? Need to make sure
      //    we don't rely on the order in which they are returned.
      //
      for (const target_type* const* p (tts); *p != nullptr; ++p)
        if (test (**p))
          r.push_back (*p);
    }

    // Next try target types derived from any of the base types (or file if
    // there are no base types).
    //
    const target_type_map& ttm (bs.root_scope ()->root_extra->target_types);

    for (auto i (ttm.type_begin ()), e (ttm.type_end ()); i != e; ++i)
    {
      const target_type& dt (i->second);

      if (tts != nullptr)
      {
        for (const target_type* const* p (tts); *p != nullptr; ++p)
        {
          const target_type& bt (**p);

          if (dt.is_a (bt))
          {
            if (dt != bt && test (dt))
              r.push_back (&dt);

            break;
          }
        }
      }
      else
      {
        // Anything file-derived but not the file itself.
        //
        if (dt.is_a<file> () && dt != file::static_type && test (dt))
          r.push_back (&dt);
      }
    }

    return r;
  }

  void dyndep_rule::
  append_prefix (tracer& trace, prefix_map& m, const target& t, dir_path d)
  {
    // If the target directory is a sub-directory of the include directory,
    // then the prefix is the difference between the two. Otherwise, leave it
    // empty.
    //
    // The idea here is to make this "canonical" setup work auto-magically
    // (using C/C++ #include's as an example):
    //
    // 1. We include all headers with a prefix, e.g., <foo/bar>.
    //
    // 2. The library target is in the foo/ sub-directory, e.g., /tmp/foo/.
    //
    // 3. The poptions variable contains -I/tmp.
    //
    dir_path p (t.dir.sub (d) ? t.dir.leaf (d) : dir_path ());

    // We use the target's directory as out_base but that doesn't work well
    // for targets that are stashed in subdirectories. So as a heuristics we
    // are going to also enter the outer directories of the original prefix.
    // It is, however, possible, that another directory after this one will
    // produce one of these outer prefixes as its original prefix in which
    // case we should override it.
    //
    // So we are going to assign the original prefix priority value 0
    // (highest) and then increment it for each outer prefix.
    //
    auto enter = [&trace, &m] (dir_path p, dir_path d, size_t prio)
    {
      auto j (m.lower_bound (p)), e (m.end ());

      if (j != e && j->first != p)
        j = e;

      if (j == m.end ())
      {
        if (verb >= 4)
          trace << "new mapping for prefix '" << p << "'\n"
                << "  new mapping to      " << d << " priority " << prio;

        m.emplace (move (p), prefix_value {move (d), prio});
      }
      else if (p.empty ())
      {
        // For prefixless we keep all the entries since for them we have an
        // extra check (target must be explicitly spelled out in a buildfile).
        //
        if (verb >= 4)
          trace << "additional mapping for prefix '" << p << "'\n"
                << "  new mapping to      " << d << " priority " << prio;

        // Find the position where to insert according to the priority.
        // For equal priorities we use the insertion order.
        //
        do
        {
          if (j->second.priority > prio)
            break;
        }
        while (++j != e && j->first == p);

        m.emplace_hint (j, move (p), prefix_value {move (d), prio});
      }
      else
      {
        prefix_value& v (j->second);

        // We used to reject duplicates but it seems this can be reasonably
        // expected to work according to the order of, say, -I options.
        //
        // Seeing that we normally have more "specific" -I paths first, (so
        // that we don't pick up installed headers, etc), we ignore it.
        //
        if (v.directory == d)
        {
          if (v.priority > prio)
            v.priority = prio;
        }
        else if (v.priority <= prio)
        {
          if (verb >= 4)
            trace << "ignoring mapping for prefix '" << p << "'\n"
                  << "  existing mapping to " << v.directory
                  << " priority " << v.priority << '\n'
                  << "  another mapping to  " << d << " priority " << prio;
        }
        else
        {
          if (verb >= 4)
            trace << "overriding mapping for prefix '" << p << "'\n"
                  << "  existing mapping to " << v.directory
                  << " priority " << v.priority << '\n'
                  << "  new mapping to      " << d << " priority " << prio;

          v.directory = move (d);
          v.priority = prio;
        }
      }
    };

    // Enter all outer prefixes, including prefixless.
    //
    // The prefixless part is fuzzy but seems to be doing the right thing
    // ignoring/overriding-wise, at least in cases where one of the competing
    // include search paths is a subdirectory of another.
    //
    for (size_t prio (0);; ++prio)
    {
      bool e (p.empty ());
      enter ((e ? move (p) : p), (e ? move (d) : d), prio);
      if (e)
        break;
      p = p.directory ();
    }
  }

  bool dyndep_rule::srcout_builder::
  next (dir_path&& d)
  {
    // Ignore any paths containing '.', '..' components. Allow any directory
    // separators though (think -I$src_root/foo on Windows).
    //
    if (d.absolute () && d.normalized (false))
    {
      // If we have a candidate out_base, see if this is its src_base.
      //
      if (prev_ != nullptr)
      {
        const dir_path& bp (prev_->src_path ());

        if (d.sub (bp))
        {
          if (diff_.empty () || d.leaf (bp) == diff_)
          {
            // We've got a pair.
            //
            map_.emplace (move (d), prev_->out_path () / diff_);
            prev_ = nullptr; // Taken.
            return true;
          }
        }

        // Not a pair. Fall through to consider as out_base.
        //
        prev_ = nullptr;
      }

      // See if this path is inside a project with an out of source build and is
      // in the out directory tree.
      //
      const scope& bs (ctx_.scopes.find_out (d));
      if (bs.root_scope () != nullptr)
      {
        if (!bs.out_eq_src ())
        {
          const dir_path& bp (bs.out_path ());

          bool e;
          if ((e = (d == bp)) || d.sub (bp))
          {
            prev_ = &bs;
            if (e)
              diff_.clear ();
            else
              diff_ = d.leaf (bp);
          }
        }
      }
    }
    else
      prev_ = nullptr;

    return false;
  }

  static pair<const file*, bool>
  enter_file_impl (
    tracer& trace, const char* what,
    action a, const scope& bs, const target& t,
    path& fp, bool cache, bool norm,
    bool insert,
    bool dynamic,
    const function<dyndep_rule::map_extension_func>& map_extension,
    const target_type& fallback,
    const function<dyndep_rule::prefix_map_func>& get_pfx_map,
    const dyndep_rule::srcout_map& so_map)
  {
    // NOTE: see enter_header() caching logic if changing anyting here with
    //       regards to the target and base scope usage.

    // Find or maybe insert the target.
    //
    // If insert is false, then don't consider dynamically-created targets
    // (i.e., those that are not real or implied) unless dynamic is true, in
    // which case return the target that would have been inserted.
    //
    // The directory is only moved from if insert is true. Note that it must
    // be normalized.
    //
    auto find = [&trace, what, &bs, &t,
                 &map_extension,
                 &fallback] (dir_path&& d,
                             path&& f,
                             bool insert,
                             bool dynamic = false) -> const file*
    {
      // Split the file into its name part and extension. Here we can assume
      // the name part is a valid filesystem name.
      //
      // Note that if the file has no extension, we record an empty extension
      // rather than NULL (which would signify that the default extension
      // should be added).
      //
      string e (f.extension ());
      string n (move (f).string ());

      if (!e.empty ())
        n.resize (n.size () - e.size () - 1); // One for the dot.

      // See if this directory is part of any project and if so determine
      // the target type.
      //
      // While at it also determine if this target is from the src or out
      // tree of said project.
      //
      dir_path out;

      // It's possible the extension-to-target type mapping is ambiguous (for
      // example, because both C and C++-language headers use the same .h
      // extension). In this case we will first try to find one that matches
      // an explicit target (similar logic to when insert is false).
      //
      small_vector<const target_type*, 2> tts;

      // Note that the path can be in out or src directory and the latter
      // can be associated with multiple scopes. So strictly speaking we
      // need to pick one that is "associated" with us. But that is still a
      // TODO (see scope_map::find() for details) and so for now we just
      // pick the first one (it's highly unlikely the source file extension
      // mapping will differ based on the configuration).
      //
      // Note that we also need to remember the base scope for search() below
      // (failed that, search_existing_file() will refuse to look).
      //
      const scope* s (nullptr);
      {
        // While we cannot accurately associate in the general case, we can do
        // so if the path belongs to this project.
        //
        const scope& rs (*bs.root_scope ());
        bool src (false);
        if (d.sub (rs.out_path ()) ||
            (src = (!rs.out_eq_src () && d.sub (rs.src_path ()))))
        {
          if (map_extension != nullptr)
            tts = map_extension (bs, n, e);

          if (src)
            out = out_src (d, rs);

          s = &bs;
        }
        else
        {
          const scope& bs (**t.ctx.scopes.find (d).first);
          if (const scope* rs = bs.root_scope ())
          {
            if (map_extension != nullptr)
              tts = map_extension (bs, n, e);

            if (!rs->out_eq_src () && d.sub (rs->src_path ()))
              out = out_src (d, *rs);

            s = &bs;
          }
        }
      }

      // If it is outside any project, or the project doesn't have such an
      // extension, use the fallback target type.
      //
      if (tts.empty ())
      {
        // If the project doesn't "know" this extension then we can't possibly
        // find a real or implied target of this type.
        //
        if (!insert && !dynamic)
        {
          l6 ([&]{trace << "unknown " << what << ' ' << n << " extension '"
                        << e << "'";});
          return nullptr;
        }

        tts.push_back (&fallback);
      }

      // Find or insert target.
      //
      // Note that in case of the target type ambiguity we first try to find
      // an explicit target that resolves this ambiguity.
      //
      const target* r (nullptr);

      if (!insert || tts.size () > 1)
      {
        // Note that we skip any target type-specific searches (like for an
        // existing file) and go straight for the target object since we need
        // to find the target explicitly spelled out.
        //
        // Also, it doesn't feel like we should be able to resolve an absolute
        // path with a spelled-out extension to multiple targets.
        //
        const target* f (nullptr);

        for (size_t i (0), m (tts.size ()); i != m; ++i)
        {
          const target_type& tt (*tts[i]);

          if (const target* x = t.ctx.targets.find (tt, d, out, n, e, trace))
          {
            // What would be the harm in reusing a dynamically-inserted target
            // if there is no buildfile-mentioned one? Probably none (since it
            // can't be updated) except that it will be racy: sometimes we
            // will reuse the dynamic, sometimes we will insert a new one. And
            // we don't like racy.
            //
            // Note that we can't only check for real targets and must include
            // implied ones because pre-entered members of a target group
            // (e.g., cli.cxx) are implied.
            //
            if (operator>= (x->decl, target_decl::implied)) // @@ VC14
            {
              r = x;
              break;
            }
            else
            {
              // Cache the dynamic target corresponding to tts[0] since that's
              // what we will be inserting (see below).
              //
              if ((insert || dynamic) && i == 0)
                f = x;

              l6 ([&]{trace << "dynamic target with target type " << tt.name;});
            }
          }
          else
            l6 ([&]{trace << "no target with target type " << tt.name;});
        }

        // Note: we can't do this because of the in source builds where there
        // won't be explicit targets for non-generated files.
        //
        // This should be harmless, however, since in our world generated file
        // are spelled-out as explicit targets. And if not, we will still get
        // an error, just a bit less specific.
        //
#if 0
        if (r == nullptr && insert)
        {
          f = d / n;
          if (!e.empty ())
          {
            f += '.';
            f += e;
          }

          diag_record dr (fail);
          dr << "ambiguous mapping of " << what ' ' << f << " to target type";
          for (const target_type* tt: tts)
            dr << info << "could be " << tt->name << "{}";
          dr << info << "spell-out its target to resolve this ambiguity";
        }
#endif

        if (r == nullptr && f != nullptr)
          r = f;
      }

      // @@ OPT: move d, out, n
      //
      if (r == nullptr && insert)
        r = &search (t, *tts[0], d, out, n, &e, s);

      return static_cast<const file*> (r);
    };

    // If it's not absolute then it either does not (yet) exist or is a
    // relative ""-include (see init_args() for details). Reduce the second
    // case to absolute.
    //
    // Note: we now always use absolute path to the translation unit so this
    // no longer applies. But let's keep it for posterity.
    //
    // Also note that we now assume (see cc::compile_rule::enter_header()) a
    // relative path signifies a generated header.
    //
#if 0
    if (f.relative () && rels.relative ())
    {
      // If the relative source path has a directory component, make sure it
      // matches since ""-include will always start with that (none of the
      // compilers we support try to normalize this path). Failed that we may
      // end up searching for a generated header in a random (working)
      // directory.
      //
      const string& fs (f.string ());
      const string& ss (rels.string ());

      size_t p (path::traits::rfind_separator (ss));

      if (p == string::npos || // No directory.
          (fs.size () > p + 1 &&
           path::traits::compare (fs.c_str (), p, ss.c_str (), p) == 0))
      {
        path t (work / f); // The rels path is relative to work.

        if (exists (t))
          f = move (t);
      }
    }
#endif

    const file* pt (nullptr);
    bool remapped (false);

    // If relative then it does not exist.
    //
    if (fp.relative ())
    {
      // This is probably as often an error as an auto-generated file, so
      // trace at level 4.
      //
      l4 ([&]{trace << "non-existent " << what << " '" << fp << "'";});

      if (get_pfx_map != nullptr)
      {
        fp.normalize ();

        // The relative path might still contain '..' (e.g., ../foo.hxx;
        // presumably ""-include'ed). We don't attempt to support auto-
        // generated files with such inclusion styles.
        //
        if (fp.normalized ())
        {
          const dyndep_rule::prefix_map& pfx_map (get_pfx_map (a, bs, t));

          // First try the whole file. Then just the directory.
          //
          // @@ Has to be a separate map since the prefix can be the same as
          //    the file name.
          //
          // auto i (pfx_map->find (f));

          // Find the most qualified prefix of which we are a sub-path.
          //
          if (!pfx_map.empty ())
          {
            dir_path d (fp.directory ());
            auto p (pfx_map.sup_range (d));

            if (p.first != p.second)
            {
              // Note that we can only have multiple entries for the
              // prefixless mapping.
              //
              dir_path pd; // Reuse.
              for (auto i (p.first); i != p.second; ++i)
              {
                // Note: value in pfx_map is not necessarily canonical.
                //
                pd = i->second.directory;
                pd.canonicalize ();

                l4 ([&]{trace << "try prefix '" << d << "' mapped to " << pd;});

                // If this is a prefixless mapping, then only use it if we can
                // resolve it to an existing target (i.e., it is explicitly
                // spelled out in a buildfile). @@ Hm, I wonder why, it's not
                // like we can generate any file without an explicit target.
                // Maybe for diagnostics (i.e., we will actually try to build
                // something there instead of just saying no mapping).
                //
                if (i->first.empty ())
                  pt = find (pd / d, fp.leaf (), false);
                else
                  pt = find (pd / d, fp.leaf (), insert, dynamic);

                if (pt != nullptr)
                {
                  fp = pd / fp;
                  l4 ([&]{trace << "mapped as auto-generated " << fp;});
                  break;
                }
                else
                  l4 ([&]{trace << "no explicit target in " << pd;});
              }
            }
            else
              l4 ([&]{trace << "no prefix map entry for '" << d << "'";});
          }
          else
            l4 ([&]{trace << "prefix map is empty";});
        }
      }
    }
    else
    {
      // Normalize the path unless it is already normalized. This is also
      // where we handle src-out remap which is not needed if cached.
      //
      if (!norm)
        normalize_external (fp, what);

      if (!cache)
      {
        if (!so_map.empty ())
        {
          // Find the most qualified prefix of which we are a sub-path.
          //
          auto i (so_map.find_sup (fp));
          if (i != so_map.end ())
          {
            // Ok, there is an out tree for this file. Remap to a path from
            // the out tree and see if there is a target for it. Note that the
            // value in so_map is not necessarily canonical.
            //
            dir_path d (i->second);
            d /= fp.leaf (i->first).directory ();
            d.canonicalize ();

            pt = find (move (d), fp.leaf (), false); // d is not moved from.

            if (pt != nullptr)
            {
              path p (d / fp.leaf ());
              l4 ([&]{trace << "remapping " << fp << " to " << p;});
              fp = move (p);
              remapped = true;
            }
          }
        }
      }

      if (pt == nullptr)
      {
        l6 ([&]{trace << (insert ? "entering " : "finding ") << fp;});
        pt = find (fp.directory (), fp.leaf (), insert, dynamic);
      }
    }

    return make_pair (pt, remapped);
  }

  pair<const file*, bool> dyndep_rule::
  enter_file (tracer& trace, const char* what,
              action a, const scope& bs, target& t,
              path& fp, bool cache, bool norm,
              const function<map_extension_func>& map_ext,
              const target_type& fallback,
              const function<prefix_map_func>& pfx_map,
              const srcout_map& so_map)
  {
    return enter_file_impl (trace, what,
                            a, bs, t,
                            fp, cache, norm,
                            true /* insert */, false,
                            map_ext, fallback, pfx_map, so_map);
  }

  pair<const file*, bool> dyndep_rule::
  find_file (tracer& trace, const char* what,
             action a, const scope& bs, const target& t,
             path& fp, bool cache, bool norm,
             bool dynamic,
             const function<map_extension_func>& map_ext,
             const target_type& fallback,
             const function<prefix_map_func>& pfx_map,
             const srcout_map& so_map)
  {
    return enter_file_impl (trace, what,
                            a, bs, t,
                            fp, cache, norm,
                            false /* insert */, dynamic,
                            map_ext, fallback, pfx_map, so_map);
  }

  static pair<const file&, bool>
  inject_group_member_impl (action a, const scope& bs, mtime_target& g,
                            path f, string n, string e,
                            const target_type& tt,
                            const function<dyndep_rule::group_filter_func>& fl,
                            bool skip_match)
  {
    // NOTE: see adhoc_rule_regex_pattern::apply_group_members() for a variant
    //       of the same code.

    // We expect that nobody else can insert these members (seems reasonable
    // seeing that their names are dynamically discovered).
    //
    auto l (search_new_locked (
              bs.ctx,
              tt,
              f.directory (),
              dir_path (), // Always in out.
              move (n),
              &e,
              &bs));

    const file& t (l.first.as<file> ()); // Note: non-const only if have lock.

    bool locked (l.second);
    if (locked)
    {
      l.first.group = &g;
      l.second.unlock ();

      // We don't need to match the group recipe directy from ad hoc
      // recipes/rules due to the special semantics for explicit group members
      // in match_rule(). This is what skip_match is for.
      //
      if (skip_match)
      {
        t.path (move (f));
        return pair<const file&, bool> (t, true);
      }
    }
    else
    {
      if (fl != nullptr && !fl (g, t))
        return pair<const file&, bool> (t, false);
    }

    // Check if we already belong to this group. Note that this not a mere
    // optimization since we may be in the member->group->member chain and
    // trying to lock the member the second time would deadlock (this can be
    // triggered, for example, by dist, which sort of depends on such members
    // directly @@ maybe this should be fixed there?).
    //
    if (t.group == &g && skip_match) // Note: group query is atomic.
      t.path (move (f));
    else
    {
      // This shouldn't normally fail since we are the only ones that should
      // know about this target (otherwise why is it dynamicaly discovered).
      // However, nothing prevents the user from depending on such a target,
      // however misguided.
      //
      target_lock tl (lock (a, t));

      if (!tl)
        fail << "group " << g << " member " << t << " is already matched" <<
          info << "dynamically extracted group members cannot be used as "
               << "prerequisites directly, only via group";

      if (!locked)
      {
        if (t.group == nullptr)
          tl.target->group = &g;
        else if (t.group != &g)
          fail << "group " << g << " member " << t
               << " is already member of group " << *t.group;
      }

      t.path (move (f));

      if (!skip_match)
      {
        match_inc_dependents (a, g);
        match_recipe (tl, group_recipe);
      }
    }

    return pair<const file&, bool> (t, true);
  }

  const file& dyndep_rule::
  inject_group_member (action a, const scope& bs, mtime_target& g,
                       path f, const target_type& tt)
  {
    path n (f.leaf ());
    string e (n.extension ());
    n.make_base ();

    return inject_group_member_impl (a, bs, g,
                                     move (f), move (n).string (), move (e),
                                     tt,
                                     nullptr /* filter */,
                                     false).first;
  }

  static const target_type&
  map_target_type (const char* what,
                   const scope& bs,
                   const path& f, const string& n, const string& e,
                   const function<dyndep_rule::map_extension_func>& map_ext,
                   const target_type& fallback)
  {
    // Map extension to the target type, falling back to the fallback type.
    //
    small_vector<const target_type*, 2> tts;
    if (map_ext != nullptr)
      tts = map_ext (bs, n, e);

    // Not sure what else we can do in this case.
    //
    if (tts.size () > 1)
    {
      diag_record dr (fail);

      dr << "mapping of " << what << " target file " << f
         << " to target type is ambiguous";

      for (const target_type* tt: tts)
        dr << info << "can be " << tt->name << "{}";
    }

    const target_type& tt (tts.empty () ? fallback : *tts.front ());

    if (!tt.is_a<file> ())
    {
      fail << what << " target file " << f << " mapped to non-file-based "
           << "target type " << tt.name << "{}";
    }

    return tt;
  }

  pair<const file&, bool> dyndep_rule::
  inject_group_member (const char* what,
                       action a, const scope& bs, mtime_target& g,
                       path f,
                       const function<map_extension_func>& map_ext,
                       const target_type& fallback,
                       const function<group_filter_func>& filter,
                       bool skip_match)
  {
    path n (f.leaf ());
    string e (n.extension ());
    n.make_base ();

    // Map extension to the target type, falling back to the fallback type.
    //
    const target_type& tt (
      map_target_type (what, bs, f, n.string (), e, map_ext, fallback));

    return inject_group_member_impl (a, bs, g,
                                     move (f), move (n).string (), move (e),
                                     tt,
                                     filter,
                                     skip_match);
  }

  pair<const file&, bool> dyndep_rule::
  inject_adhoc_group_member (const char* what,
                             action, const scope& bs, target& t,
                             path f,
                             const function<map_extension_func>& map_ext,
                             const target_type& fallback)
  {
    path n (f.leaf ());
    string e (n.extension ());
    n.make_base ();

    // Map extension to the target type, falling back to the fallback type.
    //
    const target_type& tt (
      map_target_type (what, bs, f, n.string (), e, map_ext, fallback));

    // Assume nobody else can insert these members (seems reasonable seeing
    // that their names are dynamically discovered).
    //
    auto l (search_new_locked (
              bs.ctx,
              tt,
              f.directory (),
              dir_path (), // Always in out.
              move (n).string (),
              &e,
              &bs));

    file* ft (&l.first.as<file> ()); // Note: non-const only if locked.

    // Skip if this is one of the static targets (or a duplicate of the
    // dynamic target).
    //
    // In particular, we expect to skip all the targets that we could not lock
    // (e.g., in case all of this has already been done for the previous
    // operation in a batch; make sure to test `update update update` and
    // `update clean update ...` batches if changing anything here).
    //
    // While at it also find the ad hoc members list tail.
    //
    const_ptr<target>* tail (&t.adhoc_member);
    for (target* m (&t); m != nullptr; m = m->adhoc_member)
    {
      if (ft == m)
      {
        tail = nullptr;
        break;
      }

      tail = &m->adhoc_member;
    }

    if (tail == nullptr)
      return pair<const file&, bool> (*ft, false);

    if (!l.second)
      fail << "dynamic " << what << " target " << *ft << " already exists "
           << "and cannot be made ad hoc member of group " << t;

    ft->group = &t;
    l.second.unlock ();

    // We need to be able to distinguish static targets from dynamic (see the
    // static set hashing in adhoc_buildscript_rule::apply() for details).
    //
    assert (ft->decl != target_decl::real);

    *tail = ft;
    ft->path (move (f));

    return pair<const file&, bool> (*ft, true);
  }
}