DependencyResolver.pm 23.8 KB
Newer Older
1
2
package ksb::DependencyResolver;

3
4
# Class: DependencyResolver
#
5
6
7
8
9
10
# This module handles resolving dependencies between modules. Each "module"
# from the perspective of this resolver is simply a module full name, as
# given by the KDE Project database.  (e.g. extragear/utils/kdesrc-build)

use strict;
use warnings;
11
use 5.014;
12

13
our $VERSION = '0.20';
14

15
use ksb::BuildException;
16
17
18
19
use ksb::Debug;
use ksb::Util;
use List::Util qw(first);

20
21
# Constructor: new
#
22
23
24
25
26
27
28
# Constructs a new <DependencyResolver>.
#
# Parameters:
#
#   moduleFactoryRef - Reference to a sub that creates ksb::Modules from
#     kde-project module names. Used for ksb::Modules for which the user
#     requested recursive dependency inclusion.
29
30
31
#
# Synposis:
#
32
# > my $resolver = new DependencyResolver($modNewRef);
33
34
# > $resolver->readDependencyData(open my $fh, '<', 'file.txt');
# > $resolver->resolveDependencies(@modules);
35
36
37
sub new
{
    my $class = shift;
38
    my $moduleFactoryRef = shift;
39
40

    my $self = {
41
42
43
44
45
46
        # hash table mapping short module names (m) to a hashref key by branch
        # name, the value of which is yet another hashref (see
        # readDependencyData). Note that this assumes KDE git infrastructure
        # ensures that all full module names (e.g.
        # kde/workspace/plasma-workspace) map to a *unique* short name (e.g.
        # plasma-workspace) by stripping leading path components
47
        dependenciesOf  => { },
48
49
50
51

        # hash table mapping a wildcarded module name with no branch to a
        # listref of module:branch dependencies.
        catchAllDependencies => { },
52
53
54
55
56

        # reference to a sub that will properly create a ksb::Module from a
        # given kde-project module name. Used to support automatically adding
        # dependencies to a build.
        moduleFactoryRef => $moduleFactoryRef,
57
58
59
60
61
    };

    return bless $self, $class;
}

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
our @WELL_KNOWN_SPECIAL_BUILD_SYSTEMS = (
    'Qt5'
);

our @WELL_KNOWN_SPECIAL_MODULE_NAMES = (
    'Qt',
    'Qt5'
);

# Function: _isSpecialModuleDependency
#
# Internal:
#
# This helper function does the actual work of determining whether or not a
# given ksb::Module looks like a well known 'special' dependency. (The special
# dependencies are ignored when reading dependency data by default, in favour
# of a system-wide installed version of the same software).
#
sub _isSpecialModuleDependency
{
    my $module = shift;

    #
    # linear scans should be plenty fast, despite resulting O(n*m) complexity
    # because the number of special modules (m) is so low.
    # use a manual loop to return early if the module turns out to be 'special'
    #

    # first try to match on well known build system types:
    # this lets us support special 'sub'-modules easily, e.g. submodules of Qt
    for my $build (@WELL_KNOWN_SPECIAL_BUILD_SYSTEMS)
    {
        if($module->buildSystemType() eq $build)
        {
            return 1;
        }
    }

    # fall back to matching against well known module names
    # lets us support 'special' modules that otherwise look like KDE ones
    for my $name (@WELL_KNOWN_SPECIAL_MODULE_NAMES)
    {
        if ($module->name() eq $name)
        {
            return 1;
        }
    }

    return 0;
}

# Function: filterSpecialDependencies
#
# Filters a given list modules, returning a copy containing only 'special'
# modules. The returned list can be used with readDependencyData() to prevent
# these 'special' dependencies from being ignored by default.
#
# Parameters:
#  $@_ - A list of ksb::Module objects to filter for 'special' dependencies
#
sub filterSpecialDependencies
{
    return grep { _isSpecialModuleDependency($_) } @_;
}

127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# Function: shortenModuleName
#
# Internal:
#
# This method returns the 'short' module name of kde-project full project paths.
# E.g. 'kde/kdelibs/foo' would be shortened to 'foo'.
#
# This is a static function, not an object method.
#
# Parameters:
#
#  path - A string holding the full module virtual path
#
# Returns:
#
#  The module name.
sub _shortenModuleName
{
    my $name = shift;
    $name =~ s{^.*/}{}; # Uses greedy capture by default
    return $name;
}

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
# Function: _inSpecialDependencyWhitelist
#
# Internal:
#
# Helper function to determine whether or not a given depndency (short) item
# name is whitelisted as part of 'special' dependencies
#
# Parameters:
#
#  name - A string which should contain a valid module name (e.g. kate)
#  whitelistedModules - a whitelist of modules to consult/check with
#
# Returns:
#
#  Truthy if the given module name is whitelisted
#
sub _inSpecialDependencyWhitelist
{
    my $name = shift;
    my @whitelistedModules = @_;

    for my $module (@whitelistedModules)
    {
        if ($module->name() eq $name)
        {
            return 1;
        }
    }

    return 0;
}

# Function: _suppressSpecialDependency
#
# Internal:
#
# Helper function to determine whether or not a dependency should be ignored
# by default. To check whether or not a given dependency declaration should
# be suppressed, check both the sourceItem and dependentItem against this
# function.
#
# Parameters:
#
#  item - A string containing an "item" from a dependency data declaration
#  specialModules - whitelist of special dependencies which do not need to
#                   be suppressed
#
# Returns:
#
#  Truthy if the dependency should be suppressed
#
sub _suppressSpecialDependency
{
    my $item = shift;
    my @specialModules = @_;

    if ($item =~ /^\s*Qt/)
    {
        my $itemName = _shortenModuleName($item);
        return ! _inSpecialDependencyWhitelist($itemName, @specialModules);
    }

    return 0;
}

215
216
# Method: readDependencyData
#
217
# Reads in dependency data in a pseudo-Makefile format.
218
219
# See kde-build-metadata/dependency-data.
#
220
221
222
223
224
225
# Parameters:
#  $self - The DependencyResolver object.
#  $fh   - Filehandle to read dependencies from (should already be open).
#
# Exceptions:
#  Can throw an exception on I/O errors or malformed dependencies.
226
227
228
229
sub readDependencyData
{
    my $self = assert_isa(shift, 'ksb::DependencyResolver');
    my $fh = shift;
230
    my @specialModules = @_;
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

    my $dependenciesOfRef  = $self->{dependenciesOf};
    my $dependencyAtom =
        qr/
        ^\s*        # Clear leading whitespace
        ([^\[:\s]+) # (1) Capture anything not a [, :, or whitespace (dependent item)
        \s*         # Clear whitespace we didn't capture
        (?:\[       # Open a non-capture group...
            ([^\]:\s]+) # (2) Capture branch name without brackets
        ])?+        # Close group, make optional, no backtracking
        \s*         # Clear whitespace we didn't capture
        :
        \s*
        ([^\s\[]+)  # (3) Capture all non-whitespace (source item)
        (?:\s*\[     # Open a non-capture group...
            ([^\]\s]+) # (4) Capture branch name without brackets
        ])?+        # Close group, make optional, no backtracking
        \s*$        # Ensure no trailing cruft. Any whitespace should end line
        /x;         # /x Enables extended whitespace mode

    while(my $line = <$fh>) {
        # Strip comments, skip empty lines.
        $line =~ s{#.*$}{};
        next if $line =~ /^\s*$/;

        if ($line !~ $dependencyAtom) {
            croak_internal("Invalid line $line when reading dependency data.");
        }

        my ($dependentItem, $dependentBranch,
            $sourceItem,    $sourceBranch) = $line =~ $dependencyAtom;

263
        # Ignore "catch-all" dependencies where the source is the catch-all
264
265
266
267
268
        if ($sourceItem =~ m,\*$,) {
            warning ("\tIgnoring dependency on wildcard module grouping " .
                     "on line $. of kde-build-metadata/dependency-data");
            next;
        }
269

270
271
272
273
274
275
276
277
        #
        # assume there are system-wide versions for certain 'special'
        # dependencies by default. In those cases, ignore dependency data
        # by defaul unless we think we can actually build them,
        # i.e. the modules are whitelisted in @specialModules
        #
        next if _suppressSpecialDependency($sourceItem, @specialModules) ||
                _suppressSpecialDependency($dependentItem, @specialModules);
278

279
280
281
        $dependentBranch ||= '*'; # If no branch, apply catch-all flag
        $sourceBranch ||= '*';

282
283
        # Source can never be a catch-all so we can shorten early. Also,
        # we *must* shorten early to avoid a dependency on a long path.
284
        $sourceItem = _shortenModuleName($sourceItem);
285

286
287
288
289
290
291
292
        # Handle catch-all dependent groupings
        if ($dependentItem =~ /\*$/) {
            $self->{catchAllDependencies}->{$dependentItem} //= [ ];
            push @{$self->{catchAllDependencies}->{$dependentItem}}, "$sourceItem:$sourceBranch";
            next;
        }

293
294
        $dependentItem = _shortenModuleName($dependentItem);

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
        # Initialize with hashref if not already defined. The hashref will hold
        #     - => [ ] (list of explicit *NON* dependencies of item:$branch),
        #     + => [ ] (list of dependencies of item:$branch)
        #
        # Each dependency item is tracked at the module:branch level, and there
        # is always at least an entry for module:*, where '*' means branch
        # is unspecified and should only be used to add dependencies, never
        # take them away.
        #
        # Finally, all (non-)dependencies in a list are also of the form
        # fullname:branch, where "*" is a valid branch.
        $dependenciesOfRef->{"$dependentItem:*"} //= {
            '-' => [ ],
            '+' => [ ],
        };

        # Create actual branch entry if not present
        $dependenciesOfRef->{"$dependentItem:$dependentBranch"} //= {
            '-' => [ ],
            '+' => [ ],
        };

        my $depKey = (index($sourceItem, '-') == 0) ? '-' : '+';
        $sourceItem =~ s/^-//;

        push @{$dependenciesOfRef->{"$dependentItem:$dependentBranch"}->{$depKey}},
             "$sourceItem:$sourceBranch";
322
    }
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344

    $self->_canonicalizeDependencies();
}

# Function: _canonicalizeDependencies
#
# Ensures that all stored dependencies are stored in a way that allows for
# reproducable dependency ordering (assuming the same dependency items and same
# selectors are used).
#
# Parameters: none
#
# Returns: none
sub _canonicalizeDependencies
{
    my $self = shift;
    my $dependenciesOfRef  = $self->{dependenciesOf};

    foreach my $dependenciesRef (values %{$dependenciesOfRef}) {
        @{$dependenciesRef->{'-'}} = sort @{$dependenciesRef->{'-'}};
        @{$dependenciesRef->{'+'}} = sort @{$dependenciesRef->{'+'}};
    }
345
346
}

347
348
349
350
351
352
353
354
355
356
357
358
359
# Function: directDependenciesOf
#
# Internal:
#
# Finds and returns the direct dependencies of the given module at a given
# branch. This requires forming a list of dependencies for the module from the
# "branch neutral" dependencies, adding branch-specific dependencies, and then
# removing any explicit non-dependencies for the given branch, which is why
# this is a separate routine.
#
# Parameters:
#  dependenciesOfRef - hashref to the table of dependencies as read by
#  <readDependencyData>.
360
#  module - The short name (just the name) of the kde-project module to list
361
362
363
364
365
366
#  dependencies of.
#  branch - The branch to assume for module. This must be specified, but use
#  '*' if you have no specific branch in mind.
#
# Returns:
#  A list of dependencies. Every item of the list will be of the form
367
368
#  "$moduleName:$branch", where $moduleName will be the short kde-project module
#  name (e.g. kdelibs) and $branch will be a specific git branch or '*'.
369
#  The order of the entries within the list is not important.
370
371
372
373
374
375
376
377
378
379
380
sub _directDependenciesOf
{
    my ($dependenciesOfRef, $module, $branch) = @_;

    my $moduleDepEntryRef = $dependenciesOfRef->{"$module:*"};
    my @directDeps;
    my @exclusions;

    return unless $moduleDepEntryRef;

    push @directDeps, @{$moduleDepEntryRef->{'+'}};
381
    push @exclusions, @{$moduleDepEntryRef->{'-'}};
382
383

    $moduleDepEntryRef = $dependenciesOfRef->{"$module:$branch"};
384
    if ($moduleDepEntryRef && $branch ne '*') {
385
386
387
388
389
390
        push @directDeps, @{$moduleDepEntryRef->{'+'}};
        push @exclusions, @{$moduleDepEntryRef->{'-'}};
    }

    foreach my $exclusion (@exclusions) {
        # Remove only modules at the exact given branch as a dep.
391
392
393
        # However catch-alls can remove catch-alls.
        # But catch-alls cannot remove a specific branch, such exclusions have
        # to also be specific.
394
395
396
397
398
399
        @directDeps = grep { $_ ne $exclusion } (@directDeps);
    }

    return @directDeps;
}

400
401
402
403
# Function: makeCatchAllRules
#
# Internal:
#
404
405
406
407
# Given the internal dependency options data and a kde-project full path,
# extracts all "catch-all" rules that apply to the given item and converts
# them to standard dependencies for that item. The dependency options are
# then appropriately updated.
408
#
409
410
411
# No checks are done for logical errors (e.g. having the item depend on
# itself) and no provision is made to avoid updating a module that has
# already had its catch-all rules generated.
412
413
414
#
# Parameters:
#  optionsRef - The hashref as provided to <_visitModuleAndDependencies>
415
#  fullName - The kde-project full project path to generate dependencies for.
416
417
sub _makeCatchAllRules
{
418
    my ($optionsRef, $fullName) = @_;
419
    my $dependenciesOfRef = $optionsRef->{dependenciesOf};
420
    my $item = _shortenModuleName($fullName);
421
422
423
424
425

    while (my ($catchAll, $deps) = each %{$optionsRef->{catchAllDependencies}}) {
        my $prefix = $catchAll;
        $prefix =~ s/\*$//;

426
        if (($fullName =~ /^$prefix/) || !$prefix) {
427
428
429
430
431
432
433
434
435
436
437
            my $depEntry = "$item:*";
            $dependenciesOfRef->{$depEntry} //= {
                '-' => [ ],
                '+' => [ ],
            };

            push @{$dependenciesOfRef->{$depEntry}->{'+'}}, @{$deps};
        }
    }
}

438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
# Function: getBranchOf
#
# Internal:
#
# This function extracts the branch of the given Module by calling its
# scm object's branch-determining method. It also ensures that the branch
# returned was really intended to be a branch (as opposed to a detached HEAD);
# undef is returned when the desired commit is not a branch name, otherwise
# the user-requested branch name is returned.
sub _getBranchOf
{
    my $module = shift;
    my ($branch, $type) = $module->scm()->_determinePreferredCheckoutSource($module);

    return ($type eq 'branch' ? $branch : undef);
}

455
456
457
# Function: visitModuleAndDependencies
#
# Internal:
458
#
459
# This method is used to topographically sort dependency data. It accepts a
460
461
462
463
# <ksb::Module>, ensures that any KDE Projects it depends on (which are present
# on the build list) are re-ordered before the module, and then adds the
# <ksb::Module> to the build list (whether it is a KDE Project or not, to
# preserve ordering).
464
#
465
466
467
468
# See also _visitDependencyItemAndDependencies, which actually does most of
# the work of handling dependencies, and calls back to this function when it
# finds Modules in the build list.
#
469
470
471
472
473
# Parameters:
#  optionsRef - hashref to the module dependencies, catch-all dependencies,
#   module build list, module name to <ksb::Module> mapping, and auxiliary data
#   to see if a module has already been visited.
#  module - The <ksb::Module> to properly order in the build list.
474
475
#  level - The level of recursion of this call.
#  dependent - Identical to the same param as _visitDependencyItemAndDependencies
476
477
478
479
#
# Returns:
#  Nothing. The proper build order can be read out from the optionsRef passed
#  in.
480
481
sub _visitModuleAndDependencies
{
482
    my ($optionsRef, $module, $level, $dependentName) = @_;
483
484
    assert_isa($module, 'ksb::Module');

485
    if ($module->scmType() eq 'proj') {
486
487
        my $fullName = $module->fullProjectPath();
        my $item = _shortenModuleName($fullName);
488
489
        my $branch = _getBranchOf($module) // '*';

490
491
492
493
494
495
        # Since the initial build list is visited start to finish it is
        # possible for this module to already be in the ordered list if
        # reordering has already happened or if dependencies are included (i.e.
        # this was a dependency of some other module).
        return if ($optionsRef->{visitedItems}->{$item} // 0) == 3;

496
        $dependentName //= $item if $module->getOption('include-dependencies');
497
        _visitDependencyItemAndDependencies($optionsRef, $fullName, $branch, $level, $dependentName);
498
499

        $optionsRef->{visitedItems}->{$item} = 3; # Mark as also in build list
500
501
    }

502
503
504
505
    $module->setOption('#dependency-level', $level);
    push @{$optionsRef->{properBuildOrder}}, $module;
    --($optionsRef->{modulesNeeded});

506
507
508
    return;
}

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

#
# Work around broken kde-build-metadata: list well-known circular dependencies.
#
our @WELL_KNOWN_CIRCULAR_DEPENDENCIES = ('Qt5', 'extra-cmake-modules');

# Function: _isWellKnownCycle
#
# Internal:
#
# Unfortunately kde-build-metadata dependency data contains cycles. This
# function tests if a given circular dependency is part of a well-known cycle.
# Use it to short-circuit cycle detection in the dependency sorting logic.
#
# Parameters:
#   item - the circular dependency to check
#
# Returns:
#
# A truthy value if the given dependency name is known to be a circular
# dependency in some well-known kde-build-metadata dependency cycle.
#
sub _isWellKnownCycle
{
    my $item = shift;

    for my $cycle (@WELL_KNOWN_CIRCULAR_DEPENDENCIES)
    {
        if ($cycle eq $item)
        {
            return 1;
        }
    }
    return 0;
}

545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
# Function: visitDependencyItemAndDependencies
#
# Internal:
#
# This method is used by _visitModuleAndDependencies to account for dependencies
# by kde-project modules across dependency items that are not actually present
# in the build.
#
# For instance, if kde/foo/a depends on kde/lib/bar, and kde/lib/bar depends on
# kde/foo/baz, then /a also depends on /baz and should be ordered after /baz.
# This function accounts for that in cases such as trying to build only /a and
# /baz.
#
# Parameters:
#  optionsRef - hashref to the module dependencies, catch-all dependencies,
#   module build list, module name to <ksb::Module> mapping, and auxiliary data
#   to see if a module has already been visited.
562
563
564
565
566
#  dependencyFullItem - a string containing the full kde-projects path for the
#   the module. The full path is needed to handle wildcarded dependencies.
#  branch - The specific branch name for the dependency if
#   needed. The branch name is '*' if the branch doesn't matter (or can be
#   determined only by the branch-group in use). E.g. '*' or 'master'.
567
568
569
570
571
572
#  level - Level of recursion of the current call.
#  dependent - *if set*, is the name of the module that requires that all of its
#   dependencies be added to the build list (properly ordered) even if not
#   specifically selected in the configuration file or command line. If not set,
#   recursive dependencies are not pulled into the build even if they are not
#   in the build list.
573
574
575
#
# Returns:
#  Nothing. The proper build order can be read out from the optionsRef passed
576
577
#  in. Note that the generated build list might be longer than the build list that
#  was input, in the case that recursive dependency inclusion was requested.
578
579
sub _visitDependencyItemAndDependencies
{
580
    my ($optionsRef, $dependencyFullItem, $branch, $level, $dependentName) = @_;
581

582
583
584
585
    my $visitedItemsRef     = $optionsRef->{visitedItems};
    my $properBuildOrderRef = $optionsRef->{properBuildOrder};
    my $dependenciesOfRef   = $optionsRef->{dependenciesOf};
    my $modulesFromNameRef  = $optionsRef->{modulesFromName};
586
    my $moduleFactoryRef    = $optionsRef->{moduleFactoryRef};
587
    $level //= 0;
588

589
    my $item = _shortenModuleName($dependencyFullItem);
590

591
    debug ("dep-resolv: Visiting ", (' ' x $level), "$item");
592
593
594
595

    $visitedItemsRef->{$item} //= 0;

    # This module may have already been added to build.
596
597
598
599
600
601
602
    # 0 == Not visited
    # 1 == Currently visiting. Running into a module in visit state 1 indicates a cycle.
    # 2 == Visited, but not in build (this may happen for common dependencies with siblings, or for
    #      modules that are not in our build list but are part of dependency chain for other modules
    #      that *are* in build list).
    # 3 == Visited, placed in build queue.
    return if $visitedItemsRef->{$item} >= 2;
603
604

    # But if the value is 2 that means we've detected a cycle.
605
    if ($visitedItemsRef->{$item} == 1) {
606
607
608
609
610
        if (_isWellKnownCycle($item)) {
            debug("dep-resolv: Ignoring well known cycle: ", (' ' x $level), "$item");
            return;
        }

611
612
613
        croak_internal("Somehow there is a dependency cycle involving $item! :(");
    }

614
    $visitedItemsRef->{$item} = 1; # Mark as currently-visiting for cycle detection.
615

616
    _makeCatchAllRules($optionsRef, $dependencyFullItem);
617

618
    for my $subItem (_directDependenciesOf($dependenciesOfRef, $item, $branch)) {
619
        my ($subItemName, $subItemBranch) = ($subItem =~ m/^([^:]+):(.*)$/);
620
621
        croak_internal("Invalid dependency item: $subItem") if !$subItemName;

622
623
        next if $subItemName eq $item; # Catch-all deps might make this happen

624
625
        # This keeps us from doing a deep recursive search for dependencies
        # on an item we've already asked about.
626
        next if (($visitedItemsRef->{$subItemName} // 0) >= 2);
627

628
629
630
        debug ("\tdep-resolv: $item:$branch depends on $subItem");

        my $subModule = $modulesFromNameRef->{$subItemName};
631
632
633
634
635
636
637
        if (!$subModule && $dependentName) {
            # Dependent item not in the build, but we're including dependencies
            $subModule = $moduleFactoryRef->($subItemName);

            # May not exist, e.g. misspellings or 'virtual' dependencies like
            # kf5umbrella. But if it does, update the admin for our visit.
            if ($subModule) {
638
639
640
                $modulesFromNameRef->{$subModule->name()} = $subModule;
                ++($optionsRef->{modulesNeeded});
            }
641
        }
642

643
        if (!$subModule) {
644
            debug (" y[b[*] $item depends on $subItem, but no module builds $subItem for this run.");
645
            _visitDependencyItemAndDependencies($optionsRef, $subItemName, $subItemBranch, $level + 1, $dependentName);
646
647
        }
        else {
648
649
650
651
            if ($subItemBranch ne '*' && (_getBranchOf($subModule) // '') ne $subItemBranch) {
                my $wrongBranch = _getBranchOf($subModule) // '?';
                error (" r[b[*] $item needs $subItem, not $subItemName:$wrongBranch");
            }
652

653
            _visitModuleAndDependencies($optionsRef, $subModule, $level + 1, $dependentName);
654
655
        }

656
        last if $optionsRef->{modulesNeeded} == 0;
657
658
    }

659
660
    # Mark as done visiting.
    $visitedItemsRef->{$item} = 2;
661
662
663
    return;
}

664
# Function: resolveDependencies
665
#
666
667
668
669
# This method takes a list of Modules (real <ksb::Module> objects, not just
# module names).
#
# These modules have their dependencies resolved, and a new list of <Modules>
670
671
672
673
674
675
# is returned, containing the proper build order for the module given.
#
# Only "KDE Project" modules can be re-ordered or otherwise affect the
# build so this currently won't affect Subversion modules or "plain Git"
# modules.
#
676
677
678
679
680
681
682
683
# The dependency data must have been read in first (<readDependencyData>).
#
# Parameters:
#
#  $self    - The DependencyResolver object.
#  @modules - List of <Modules> to evaluate, in suggested build order.
#
# Returns:
684
#
685
686
687
688
#  Modules to build, with the included KDE Project modules in a valid ordering
#  based on the currently-read dependency data. KDE Project modules are only
#  re-ordered amongst themselves, other module types retain their relative
#  positions.
689
690
691
692
693
694
695
696
697
sub resolveDependencies
{
    my $self = assert_isa(shift, 'ksb::DependencyResolver');
    my @modules = @_;

    my $optionsRef = {
        visitedItems => { },
        properBuildOrder => [ ],
        dependenciesOf => $self->{dependenciesOf},
698
        catchAllDependencies => $self->{catchAllDependencies},
699
700
701

        # will map names back to their Modules
        modulesFromName => {
702
            map { $_->name() => $_ }
Michael Pyne's avatar
Michael Pyne committed
703
704
            grep { $_->scmType() eq 'proj' }
                @modules
705
        },
706

707
708
        moduleFactoryRef => $self->{moduleFactoryRef},

709
710
        # Help _visitModuleAndDependencies to optimize
        modulesNeeded => scalar @modules,
711
712
713
714
715
716
717
718
719
720
    };

    for my $module (@modules) {
        _visitModuleAndDependencies($optionsRef, $module);
    }

    return @{$optionsRef->{properBuildOrder}};
}

1;