aboutsummaryrefslogtreecommitdiff
path: root/libbuild2/algorithm.hxx
blob: dedfe33302c4319261d98a94314c062597c11986 (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
// file      : libbuild2/algorithm.hxx -*- C++ -*-
// license   : MIT; see accompanying LICENSE file

#ifndef LIBBUILD2_ALGORITHM_HXX
#define LIBBUILD2_ALGORITHM_HXX

#include <libbuild2/types.hxx>
#include <libbuild2/forward.hxx>
#include <libbuild2/utility.hxx>

#include <libbuild2/action.hxx>
#include <libbuild2/target.hxx>
#include <libbuild2/recipe.hxx>

#include <libbuild2/export.hxx>

namespace build2
{
  // The default prerequisite search implementation. It first calls the
  // prerequisite-type-specific search function. If that doesn't yield
  // anything, it creates a new target.
  //
  LIBBUILD2_SYMEXPORT const target&
  search (const target&, const prerequisite&);

  // As above but only search for an already existing target. Note that unlike
  // the above, this version can be called during the execute phase.
  //
  LIBBUILD2_SYMEXPORT const target*
  search_existing (const prerequisite&);

  // As above but cache a target searched in a custom way.
  //
  const target&
  search_custom (const prerequisite&, const target&);

  // As above but specify the prerequisite to search as a key.
  //
  LIBBUILD2_SYMEXPORT const target&
  search (const target&, const prerequisite_key&);

  // As above but return the lock if the target was newly created. Note that
  // this version can only be used on project-unqualified prerequisites.
  //
  LIBBUILD2_SYMEXPORT pair<target&, ulock>
  search_locked (const target&, const prerequisite_key&);

  // As above but this one can be called during the load and execute phases.
  //
  LIBBUILD2_SYMEXPORT const target*
  search_existing (context&, const prerequisite_key&);

  // First search for an existing target and if that doesn't yield anything,
  // creates a new target, bypassing any prerequisite-type-specific search.
  // Can be called during the load and match phases but only on project-
  // unqualified prerequisites. This version is suitable for cases where you
  // know the target is in out and cannot be possibly found in src.
  //
  LIBBUILD2_SYMEXPORT const target&
  search_new (context&, const prerequisite_key&);

  // As above but return the lock if the target was newly created.
  //
  LIBBUILD2_SYMEXPORT pair<target&, ulock>
  search_new_locked (context&, const prerequisite_key&);

  // Uniform search interface for prerequisite/prerequisite_member.
  //
  inline const target&
  search (const target& t, const prerequisite_member& p) {return p.search (t);}

  // As above but override the target type. Useful for searching for target
  // group members where we need to search for a different target type.
  //
  const target&
  search (const target&, const target_type&, const prerequisite_key&);

  pair<target&, ulock>
  search_locked (const target&, const target_type&, const prerequisite_key&);

  const target*
  search_exsiting (context&, const target_type&, const prerequisite_key&);

  const target&
  search_new (context&, const target_type&, const prerequisite_key&);

  pair<target&, ulock>
  search_new_locked (context&, const target_type&, const prerequisite_key&);

  // As above but specify the prerequisite to search as individual key
  // components. Scope can be NULL if the directory is absolute.
  //
  const target&
  search (const target&,
          const target_type&,
          const dir_path& dir,
          const dir_path& out,
          const string& name,
          const string* ext = nullptr,  // NULL means unspecified.
          const scope* = nullptr,       // NULL means dir is absolute.
          const optional<project_name>& proj = nullopt);

  pair<target&, ulock>
  search_locked (const target&,
                 const target_type&,
                 const dir_path& dir,
                 const dir_path& out,
                 const string& name,
                 const string* ext = nullptr,
                 const scope* = nullptr);

  const target*
  search_existing (context&,
                   const target_type&,
                   const dir_path& dir,
                   const dir_path& out,
                   const string& name,
                   const string* ext = nullptr,
                   const scope* = nullptr,
                   const optional<project_name>& proj = nullopt);

  const target&
  search_new (context&,
              const target_type&,
              const dir_path& dir,
              const dir_path& out,
              const string& name,
              const string* ext = nullptr,
              const scope* = nullptr);

  pair<target&, ulock>
  search_new_locked (context&,
                     const target_type&,
                     const dir_path& dir,
                     const dir_path& out,
                     const string& name,
                     const string* ext = nullptr,
                     const scope* = nullptr);

  // As above but specify the target type as template argument.
  //
  template <typename T>
  const T&
  search (const target&,
          const dir_path& dir,
          const dir_path& out,
          const string& name,
          const string* ext = nullptr,
          const scope* = nullptr);

  template <typename T>
  const T*
  search_existing (context&,
                   const dir_path& dir,
                   const dir_path& out,
                   const string& name,
                   const string* ext = nullptr,
                   const scope* = nullptr);

  // Search for a target identified by the name. The semantics is "as if" we
  // first created a prerequisite based on this name in exactly the same way
  // as the parser would and then searched based on this prerequisite. If the
  // target type is already resolved, then it can be passed as the last
  // argument.
  //
  LIBBUILD2_SYMEXPORT const target&
  search (const target&, name&&, const scope&, const target_type* = nullptr);

  // Note: returns NULL for unknown target types. Note that unlike the above
  // version, these ones can be called during the load and execute phases.
  //
  LIBBUILD2_SYMEXPORT const target*
  search_existing (const name&,
                   const scope&,
                   const dir_path& out = dir_path ());

  LIBBUILD2_SYMEXPORT const target*
  search_existing (const names&, const scope&);

  // Target match lock: a non-const target reference and the target::offset_*
  // state that has already been "achieved". Note that target::task_count
  // itself is set to busy for the duration or the lock. While at it we also
  // maintain a stack of active locks in the current dependency chain (used to
  // detect dependency cycles).
  //
  struct LIBBUILD2_SYMEXPORT target_lock
  {
    using action_type = build2::action;
    using target_type = build2::target;

    action_type  action;
    target_type* target = nullptr;
    size_t       offset = 0;
    bool         first;

    explicit operator bool () const {return target != nullptr;}

    // Note: achieved offset is preserved.
    //
    void
    unlock ();

    // Movable-only type with move-assignment only to NULL lock.
    //
    target_lock () = default;
    target_lock (target_lock&&) noexcept;
    target_lock& operator= (target_lock&&) noexcept;

    target_lock (const target_lock&) = delete;
    target_lock& operator= (const target_lock&) = delete;

    // Implementation details.
    //
    ~target_lock ();
    target_lock (action_type, target_type*, size_t, bool);

    struct data
    {
      action_type action;
      target_type* target;
      size_t offset;
      bool first;
    };

    data
    release ();

    // Tip of the stack.
    //
    static const target_lock*
    stack () noexcept;

    // Set the new and return the previous tip of the stack.
    //
    static const target_lock*
    stack (const target_lock*) noexcept;

    const target_lock* prev;

    void
    unstack ();

    struct stack_guard
    {
      explicit stack_guard (const target_lock* s): s_ (stack (s)) {}
      ~stack_guard () {stack (s_);}
      const target_lock* s_;
    };
  };

  // If this target is already locked in this dependency chain, then return
  // the corresponding lock. Return NULL otherwise (so can be used a boolean
  // predicate).
  //
  const target_lock*
  dependency_cycle (action, const target&);

  // If the target is already applied (for this action) or executed, then no
  // lock is acquired. Otherwise, unless matched is true, the target must not
  // be matched but not yet applied for this action (and if that's the case
  // and matched is true, then you get a locked target that you should
  // probably check for consistency, for exmaple, by comparing the matched
  // rule).
  //
  // @@ MT fuzzy: what if it is already in the desired state, why assert?
  //    Currently we only use it with match_recipe/rule() and if it is matched
  //    but not applied, then it's not clear why we are overriding that match.
  //
  target_lock
  lock (action, const target&, bool matched = false);

  // Add an ad hoc member to the end of the chain assuming that an already
  // existing member of this target type is the same. Return the newly added
  // or already existing target. The member directories (dir and out) are
  // expected to be absolute and normalized.
  //
  // Note that here and in find_adhoc_member() below (as well as in
  // perform_clean_extra()) we use target type (as opposed to, say, type and
  // name) as the member's identity. This fits our current needs where every
  // (rule-managed) ad hoc member has a unique target type and we have no need
  // for multiple members of the same type. This also allows us to support
  // things like changing the ad hoc member name by declaring it in a
  // buildfile.
  //
  LIBBUILD2_SYMEXPORT target&
  add_adhoc_member (target&,
                    const target_type&,
                    dir_path dir,
                    dir_path out,
                    string name);

  // If the extension is specified then it is added to the member's target
  // name.
  //
  target&
  add_adhoc_member (target&, const target_type&, const char* ext = nullptr);

  template <typename T>
  inline T&
  add_adhoc_member (target& g, const target_type& tt, const char* e = nullptr)
  {
    return static_cast<T&> (add_adhoc_member (g, tt, e));
  }

  template <typename T>
  inline T&
  add_adhoc_member (target& g, const char* e = nullptr)
  {
    return add_adhoc_member<T> (g, T::static_type, e);
  }

  // Find an ad hoc member of the specified target type returning NULL if not
  // found.
  //
  target*
  find_adhoc_member (target&, const target_type&);

  const target*
  find_adhoc_member (const target&, const target_type&);

  template <typename T>
  inline T*
  find_adhoc_member (target& g, const target_type& tt)
  {
    return static_cast<T*> (find_adhoc_member (g, tt));
  }

  template <typename T>
  inline const T*
  find_adhoc_member (const target& g, const target_type& tt)
  {
    return static_cast<const T*> (find_adhoc_member (g, tt));
  }

  template <typename T>
  inline const T*
  find_adhoc_member (const target& g)
  {
    return find_adhoc_member<T> (g, T::static_type);
  }

  template <typename T>
  inline T*
  find_adhoc_member (target& g)
  {
    return find_adhoc_member<T> (g, T::static_type);
  }

  // Match and apply a rule to the action/target with ambiguity detection.
  // This is the synchrounous match implementation that waits for completion
  // if the target is already being matched. Increment the target's dependents
  // count, which means that you should call this function with the intent to
  // also call execute*(). Translating target_state::failed to the failed
  // exception unless instructed otherwise.
  //
  // The try_match_sync() version doesn't issue diagnostics if there is no
  // rule match (but fails as match_sync() for all other errors, like rule
  // ambiguity, inability to apply, etc). The first half of the result
  // indicated whether there was a rule match.
  //
  // The unmatch argument allows optimizations that avoid calling execute*().
  // If it is unmatch::unchanged then only unmatch the target if it is known
  // to be unchanged after match. If it is unmatch::safe, then unmatch the
  // target if it is safe (this includes unchanged or if we know that someone
  // else will execute this target). Return true in first half of the pair if
  // unmatch succeeded. Always throw if failed.
  //
  enum class unmatch {none, unchanged, safe};

  target_state
  match_sync (action, const target&, bool fail = true);

  pair<bool, target_state>
  try_match_sync (action, const target&, bool fail = true);

  pair<bool, target_state>
  match_sync (action, const target&, unmatch);

  // As above but only match the target (unless already matched) without
  // applying the match (which is normally done with match_sync()). You will
  // most likely regret using this function.
  //
  LIBBUILD2_SYMEXPORT void
  match_only_sync (action, const target&);

  // Start asynchronous match. Return target_state::postponed if the
  // asynchronous operation has been started and target_state::busy if the
  // target has already been busy. Regardless of the result, match_complete()
  // must be called in order to complete the operation (except if the result
  // is target_state::failed), which has the result semantics of match_sync().
  //
  // If fail is false, then return target_state::failed if the target match
  // failed. Otherwise, throw the failed exception if keep_going is false and
  // return target_state::failed otherwise.
  //
  target_state
  match_async (action, const target&,
               size_t start_count, atomic_count& task_count,
               bool fail = true);

  target_state
  match_complete (action, const target&, bool fail = true);

  pair<bool, target_state>
  match_complete (action, const target&, unmatch);

  // As above but without incrementing the target's dependents count. Should
  // be executed with execute_direct_*().
  //
  // For async, call match_async() followed by match_direct_complete().
  //
  target_state
  match_direct_sync (action, const target&, bool fail = true);

  target_state
  match_direct_complete (action, const target&, bool fail = true);

  // Apply the specified recipe directly and without incrementing the
  // dependency counts. The target must be locked.
  //
  void
  match_recipe (target_lock&, recipe);

  // Match (but do not apply) the specified rule directly and without
  // incrementing the dependency counts. The target must be locked.
  //
  void
  match_rule (target_lock&, const rule_match&);

  // Match a "delegate rule" from withing another rules' apply() function
  // avoiding recursive matches (thus the third argument). Unless try_match is
  // true, fail if no rule is found. Otherwise return empty recipe. Note that
  // unlike match(), this function does not increment the dependents count.
  // See also the companion execute_delegate().
  //
  recipe
  match_delegate (action, target&, const rule&, bool try_match = false);

  // Incrementing the dependency counts of the specified target.
  //
  void
  match_inc_dependents (action, const target&);

  // Match (synchronously) a rule for the inner operation from withing the
  // outer rule's apply() function. See also the companion execute_inner()
  // and inner_recipe.
  //
  target_state
  match_inner (action, const target&);

  pair<bool, target_state>
  match_inner (action, const target&, unmatch);

  // The standard prerequisite search and match implementations. They call
  // search() (unless a custom is provided) and then match() (unless custom
  // returned NULL) for each prerequisite in a loop omitting out of project
  // prerequisites for the clean operation unless the target is an alias. If
  // the target is a member of a group, then first do this to the group's
  // prerequisites.
  //
  // Regarding clean, it may seem more natural to only clean prerequisites
  // that are in the same base rather than root scope. While it's often true
  // for simple projects, in more complex cases it's not unusual to have
  // common intermediate build results (object files, utility libraries, etc)
  // reside in the parent and/or sibling directories. With such arrangements,
  // cleaning only in base (even from the project root) may leave such
  // intermediate build results laying around (since there is no reason to
  // list them as prerequisites of any directory aliases). So we clean in the
  // root scope by default but any target-prerequisite relationship can be
  // marked not to trigger a clean with the clean=false prerequisite-specific
  // value (see the include variable for details).
  //
  using match_search = function<
    prerequisite_target (action,
                         const target&,
                         const prerequisite&,
                         include_type)>;

  void
  match_prerequisites (action, target&, const match_search& = nullptr);

  // As above but go into group members.
  //
  // Note that if we are cleaning, this function doesn't go into group
  // members, as an optimization (the group should clean everything up).
  //
  using match_search_member = function<
    prerequisite_target (action,
                         const target&,
                         const prerequisite_member&,
                         include_type)>;

  void
  match_prerequisite_members (action, target&,
                              const match_search_member& = nullptr);

  // As above but omit prerequisites that are not in the specified scope.
  //
  void
  match_prerequisites (action, target&, const scope&);

  void
  match_prerequisite_members (action, target&, const scope&);

  // Match (already searched) members of a group or similar prerequisite-like
  // dependencies. Similar in semantics to match_prerequisites(). Any marked
  // target pointers are skipped.
  //
  LIBBUILD2_SYMEXPORT void
  match_members (action, const target&, const target* const*, size_t);

  template <size_t N>
  inline void
  match_members (action a, const target& t, const target* (&ts)[N])
  {
    match_members (a, t, ts, N);
  }

  // As above plus if the include mask (first) and value (second) are
  // specified, then only match prerequisites that satisfy the
  // ((prerequisite_target::include & mask) == value) condition.
  //
  LIBBUILD2_SYMEXPORT void
  match_members (action,
                 const target&,
                 prerequisite_targets&,
                 size_t start = 0,
                 pair<uintptr_t, uintptr_t> include = {0, 0});

  // Unless already known, match, and, if necessary, execute the group in
  // order to resolve its members list. Note that even after that the member's
  // list might still not be available (e.g., if some wildcard/fallback rule
  // matched).
  //
  // If the action is for an outer operation, then it is changed to inner
  // which means the members are always resolved by the inner (e.g., update)
  // rule. This feels right since this is the rule that will normally do the
  // work (e.g., update) and therefore knows what it will produce (and if we
  // don't do this, then the group resolution will be racy since we will use
  // two different task_count instances for synchronization).
  //
  LIBBUILD2_SYMEXPORT group_view
  resolve_members (action, const target&);

  // Unless already known, match the target in order to resolve its group.
  //
  // Unlike the member case, a rule can only decide whether a target is a
  // member of the group in its match() since otherwise it (presumably) should
  // not match (and some other rule may).
  //
  // If the action is for an outer operation, then it is changed to inner, the
  // same as for members.
  //
  const target*
  resolve_group (action, const target&);

  // Inject a target as a "prerequisite target" (note: not a prerequisite) of
  // another target. Specifically, match (synchronously) the prerequisite
  // target and then add it to the back of the dependent target's
  // prerequisite_targets.
  //
  void
  inject (action, target&, const target& prereq);

  // Inject dependency on the target's directory fsdir{}, unless it is in the
  // src tree or is outside of any project (say, for example, an installation
  // directory). If the parent argument is true, then inject the parent
  // directory of a target that is itself a directory (name is empty). Return
  // the injected target or NULL. Normally this function is called from the
  // rule's apply() function.
  //
  // As an extension, unless prereq is false, this function will also search
  // for an existing fsdir{} prerequisite for the directory and if one exists,
  // return that (even if the target is in src tree). This can be used, for
  // example, to place output into an otherwise non-existent directory.
  //
  LIBBUILD2_SYMEXPORT const fsdir*
  inject_fsdir (action, target&, bool prereq = true, bool parent = true);

  // Execute the action on target, assuming a rule has been matched and the
  // recipe for this action has been set. This is the synchrounous executor
  // implementation that waits for completion if the target is already being
  // executed. Translate target_state::failed to the failed exception unless
  // fail is false.
  //
  target_state
  execute_sync (action, const target&, bool fail = true);

  // As above but start asynchronous execution. Return target_state::unknown
  // if the asynchrounous execution has been started and target_state::busy if
  // the target has already been busy.
  //
  // If fail is false, then return target_state::failed if the target
  // execution failed. Otherwise, throw the failed exception if keep_going is
  // false and return target_state::failed otherwise. Regardless of the
  // result, execute_complete() must be called in order to complete the
  // operation (except if the result is target_state::failed), which has the
  // result semantics of execute_sync().
  //
  target_state
  execute_async (action, const target&,
                 size_t start_count, atomic_count& task_count,
                 bool fail = true);

  target_state
  execute_complete (action, const target&);

  // Execute (synchronously) the recipe obtained with match_delegate(). Note
  // that the target's state is neither checked nor updated by this function.
  // In other words, the appropriate usage is to call this function from
  // another recipe and to factor the obtained state into the one returned.
  //
  target_state
  execute_delegate (const recipe&, action, const target&);

  // Execute (synchronously) the inner operation matched with match_inner().
  // Note that the returned target state is for the inner operation. The
  // appropriate usage is to call this function from the outer operation's
  // recipe and to factor the obtained state into the one returned (similar to
  // how we do it for prerequisites). Or, if factoring is not needed, simply
  // return inner_recipe as outer recipe.
  //
  // Note: waits for the completion if the target is busy and translates
  // target_state::failed to the failed exception.
  //
  target_state
  execute_inner (action, const target&);

  // A special version of the above that should be used for "direct" and "now"
  // execution, that is, side-stepping the normal target-prerequisite
  // relationship (so no dependents count is decremented) and execution order
  // (so this function never returns the postponed target state).
  //
  // The first version waits for the completion if the target is busy and
  // translates target_state::failed to the failed exception.
  //
  target_state
  execute_direct_sync (action, const target&, bool fail = true);

  target_state
  execute_direct_async (action, const target&,
                        size_t start_count, atomic_count& task_count,
                        bool fail = true);

  // Update the target during the match phase (by switching the phase and
  // calling execute_direct()). Return true if the target has changed or, if
  // the passed timestamp is not timestamp_unknown, it is older than the
  // target.
  //
  // Note that such a target must still be updated normally during the execute
  // phase in order to keep the dependency counts straight (at which point the
  // target state/timestamp will be re-incorporated into the result).
  //
  LIBBUILD2_SYMEXPORT bool
  update_during_match (tracer&,
                       action, const target&,
                       timestamp = timestamp_unknown);

  // As above, but update all the targets in prerequisite_targets that have
  // the specified mask in prerequisite_target::include. Return true if any of
  // them have changed.
  //
  // Note that this function spoils prerequisite_target::data (which is used
  // for temporary storage). But it resets data to 0 once done.
  //
  LIBBUILD2_SYMEXPORT bool
  update_during_match_prerequisites (
    tracer&,
    action, target&,
    uintptr_t mask = prerequisite_target::include_udm);

  // The default prerequisite execute implementation. Call execute_async() on
  // each non-ignored (non-NULL) prerequisite target in a loop and then wait
  // for their completion. Return target_state::changed if any of them were
  // changed and target_state::unchanged otherwise. If a prerequisite's
  // execution is postponed (and thus its state cannot be queried MT-safely)
  // of if the prerequisite is marked as ad hoc, then set its pointer in
  // prerequisite_targets to NULL. If count is not 0, then only the first
  // count prerequisites are executed beginning from start.
  //
  // Note that because after the call the ad hoc prerequisites are no longer
  // easily accessible, this function shouldn't be used in rules that make a
  // timestamp-based out-of-date'ness determination (which must take into
  // account such prerequisites). Instead, consider the below versions that
  // incorporate the timestamp check and do the right thing.
  //
  target_state
  straight_execute_prerequisites (action, const target&,
                                  size_t count = 0, size_t start = 0);

  // As above but iterates over the prerequisites in reverse.
  //
  target_state
  reverse_execute_prerequisites (action, const target&, size_t count = 0);

  // Call straight or reverse depending on the current mode.
  //
  target_state
  execute_prerequisites (action, const target&, size_t count = 0);

  // As above but execute prerequisites for the inner action (that have
  // been matched with match_inner()).
  //
  target_state
  straight_execute_prerequisites_inner (action, const target&,
                                        size_t count = 0, size_t start = 0);

  target_state
  reverse_execute_prerequisites_inner (action, const target&, size_t count = 0);

  target_state
  execute_prerequisites_inner (action, const target&, size_t count = 0);

  // A version of the above that also determines whether the action needs to
  // be executed on the target based on the passed timestamp and filter. If
  // count is not 0, then only the first count prerequisites are executed.
  //
  // The filter is passed each prerequisite target and is expected to signal
  // which ones should be used for timestamp comparison. If the filter is
  // NULL, then all the prerequisites are used. Note that ad hoc prerequisites
  // are always used.
  //
  // Note that the return value is an optional target state. If the target
  // needs updating, then the value is absent. Otherwise it is the state that
  // should be returned. This is used to handle the situation where some
  // prerequisites were updated but no update of the target is necessary. In
  // this case we still signal that the target was (conceptually, but not
  // physically) changed. This is important both to propagate the fact that
  // some work has been done and to also allow our dependents to detect this
  // case if they are up to something tricky (like recursively linking liba{}
  // prerequisites).
  //
  // Note that because we use mtime, this function can only be used for the
  // perform_update action.
  //
  using execute_filter = function<bool (const target&, size_t pos)>;

  optional<target_state>
  execute_prerequisites (action, const target&,
                         const timestamp&,
                         const execute_filter& = nullptr,
                         size_t count = 0);

  // As above, but execute prerequisites in reverse.
  //
  // Sometime it may be advantageous to execute prerequisites in reverse, for
  // example, to have more immediate incremental compilation or more accurate
  // progress. See cc::link_rule for background.
  //
  optional<target_state>
  reverse_execute_prerequisites (action, const target&,
                                 const timestamp&,
                                 const execute_filter& = nullptr,
                                 size_t count = 0);

  // Another version of the above that does two extra things for the caller:
  // it determines whether the action needs to be executed on the target based
  // on the passed timestamp and finds a prerequisite of the specified type
  // (e.g., a source file). If there are multiple prerequisites of this type,
  // then the first is returned (this can become important if additional
  // prerequisites of the same type get injected).
  //
  template <typename T>
  pair<optional<target_state>, const T&>
  execute_prerequisites (action, const target&,
                         const timestamp&,
                         const execute_filter& = nullptr,
                         size_t count = 0);

  pair<optional<target_state>, const target&>
  execute_prerequisites (const target_type&,
                         action, const target&,
                         const timestamp&,
                         const execute_filter& = nullptr,
                         size_t count = 0);

  template <typename T>
  pair<optional<target_state>, const T&>
  execute_prerequisites (const target_type&,
                         action, const target&,
                         const timestamp&,
                         const execute_filter& = nullptr,
                         size_t count = 0);

  // Execute members of a group or similar prerequisite-like dependencies.
  // Similar in semantics to execute_prerequisites().
  //
  // T can only be const target* or prerequisite_target. If it is the latter,
  // the ad hoc blank out semantics described in execute_prerequsites() is in
  // effect.
  //
  template <typename T>
  target_state
  straight_execute_members (context&, action, atomic_count&,
                            T[], size_t, size_t);

  template <typename T>
  target_state
  reverse_execute_members (context&, action, atomic_count&,
                           T[], size_t, size_t);

  template <typename T>
  inline target_state
  straight_execute_members (action a, const target& t,
                            T ts[], size_t c, size_t s)
  {
    return straight_execute_members (t.ctx, a, t[a].task_count, ts, c, s);
  }

  template <typename T>
  inline target_state
  reverse_execute_members (action a, const target& t,
                           T ts[], size_t c, size_t s)
  {
    return reverse_execute_members (t.ctx, a, t[a].task_count, ts, c, s);
  }

  // Call straight or reverse depending on the current mode.
  //
  template <typename T>
  target_state
  execute_members (action, const target&, T[], size_t);

  template <size_t N>
  inline target_state
  straight_execute_members (action a, const target& t, const target* (&ts)[N])
  {
    return straight_execute_members (a, t, ts, N, 0);
  }

  template <size_t N>
  inline target_state
  reverse_execute_members (action a, const target& t, const target* (&ts)[N])
  {
    return reverse_execute_members (a, t, ts, N, N);
  }

  template <size_t N>
  inline target_state
  execute_members (action a, const target& t, const target* (&ts)[N])
  {
    return execute_members (a, t, ts, N);
  }

  // Return noop_recipe instead of using this function directly.
  //
  LIBBUILD2_SYMEXPORT target_state
  noop_action (action, const target&);

  // Default action implementation which forwards to the prerequisites.  Use
  // default_recipe instead of using this function directly.
  //
  LIBBUILD2_SYMEXPORT target_state
  default_action (action, const target&);

  // Group action which calls the group's recipe. Use group_recipe instead of
  // using this function directly.
  //
  LIBBUILD2_SYMEXPORT target_state
  group_action (action, const target&);

  // Standard perform(clean) action implementation for the file target (or
  // derived). Note: also cleans ad hoc group members, if any.
  //
  LIBBUILD2_SYMEXPORT target_state
  perform_clean (action, const target&);

  // As above, but also removes the auxiliary dependency database (.d file).
  //
  LIBBUILD2_SYMEXPORT target_state
  perform_clean_depdb (action, const target&);

  // As above but clean the (non-ad hoc) target group. The group should be an
  // mtime_target and members should be files.
  //
  LIBBUILD2_SYMEXPORT target_state
  perform_clean_group (action, const target&);

  // As above but clean both the target group and depdb. The depdb file path
  // is derived from the first member file path.
  //
  LIBBUILD2_SYMEXPORT target_state
  perform_clean_group_depdb (action, const target&);

  // Helpers for custom perform(clean) implementations that, besides the
  // target and group members, can also clean extra files and directories
  // (recursively) specified as a list of either absolute paths or "path
  // derivation directives". The directive string can be NULL, or empty in
  // which case it is ignored. If the last character in a directive is '/',
  // then the resulting path is treated as a directory rather than a file. The
  // directive can start with zero or more '-' characters which indicate the
  // number of extensions that should be stripped before the new extension (if
  // any) is added (so if you want to strip the extension, specify just
  // "-"). For example:
  //
  // perform_clean_extra (a, t, {".d", ".dlls/", "-.dll"});
  //
  // The extra files/directories are removed first in the specified order
  // followed by the group member, then target itself, and, finally, the
  // prerequisites in the reverse order.
  //
  // You can also clean extra files derived from ad hoc group members that are
  // "indexed" using their target types (see add/find_adhoc_member() for
  // details).
  //
  // Note that if the target path is empty then it is assumed "unreal" and is
  // not cleaned (but its prerequisites/members still are).
  //
  using clean_extras = small_vector<const char*, 8>;

  struct clean_adhoc_extra
  {
    const target_type& type;
    clean_extras       extras;
  };

  using clean_adhoc_extras = small_vector<clean_adhoc_extra, 2>;

  // If show_adhoc_members is true, then print the entire ad hoc group instead
  // of just the primary member at verbosity level 1 (see print_diag() for
  // details). Note that the default is false because normally a rule
  // implemented in C++ would only use an ad hoc group for subordiate members
  // (.pdb, etc) and would use a dedicate target group type if the members
  // are equal.
  //
  LIBBUILD2_SYMEXPORT target_state
  perform_clean_extra (action, const file&,
                       const clean_extras&,
                       const clean_adhoc_extras& = {},
                       bool show_adhoc_members = false);

  inline target_state
  perform_clean_extra (action a, const file& f,
                       initializer_list<const char*> e,
                       bool show_adhoc_members = false)
  {
    return perform_clean_extra (a, f, clean_extras (e), {}, show_adhoc_members);
  }

  // Similar to perform_clean_group() but with extras similar to
  // perform_clean_extra(). Note that the extras are derived from the group
  // "path" (g.dir / g.name).
  //
  LIBBUILD2_SYMEXPORT target_state
  perform_clean_group_extra (action, const mtime_target&, const clean_extras&);

  inline target_state
  perform_clean_group_extra (action a, const mtime_target& g,
                             initializer_list<const char*> e)
  {
    return perform_clean_group_extra (a, g, clean_extras (e));
  }

  // Update/clean a backlink issuing appropriate diagnostics at appropriate
  // levels depending on the overload and the changed argument.
  //
  // Note that these functions assume (target.leaf() == link.leaf ()).
  //
  enum class backlink_mode
  {
    link,      // Make a symbolic link if possible, hard otherwise.
    symbolic,  // Make a symbolic link.
    hard,      // Make a hard link.
    copy,      // Make a copy.
    overwrite  // Copy over but don't remove on clean (committed gen code).
  };

  LIBBUILD2_SYMEXPORT void
  update_backlink (const file& target,
                   const path& link,
                   bool changed,
                   backlink_mode = backlink_mode::link);

  LIBBUILD2_SYMEXPORT void
  update_backlink (context&,
                   const path& target,
                   const path& link,
                   bool changed,
                   backlink_mode = backlink_mode::link);

  // Note: verbosity should be 2 or greater.
  //
  LIBBUILD2_SYMEXPORT void
  update_backlink (context&,
                   const path& target,
                   const path& link,
                   backlink_mode = backlink_mode::link,
                   uint16_t verbosity = 3);

  // Note: verbosity should be 2 or greater.
  //
  LIBBUILD2_SYMEXPORT void
  clean_backlink (context&,
                  const path& link,
                  uint16_t verbosity,
                  backlink_mode = backlink_mode::link);
}

#include <libbuild2/algorithm.ixx>

#endif // LIBBUILD2_ALGORITHM_HXX