cmComputeTargetDepends.cxx 21 KB
Newer Older
1
2
3
/*============================================================================
  CMake - Cross Platform Makefile Generator
  Copyright 2000-2009 Kitware, Inc., Insight Software Consortium
4

5
6
  Distributed under the OSI-approved BSD License (the "License");
  see accompanying file Copyright.txt for details.
7

8
9
10
11
  This software is distributed WITHOUT ANY WARRANTY; without even the
  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  See the License for more information.
============================================================================*/
12
13
#include "cmComputeTargetDepends.h"

14
#include "cmComputeComponentGraph.h"
15
16
17
#include "cmGlobalGenerator.h"
#include "cmLocalGenerator.h"
#include "cmMakefile.h"
18
#include "cmSourceFile.h"
19
#include "cmState.h"
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "cmSystemTools.h"
#include "cmTarget.h"
#include "cmake.h"

#include <algorithm>

#include <assert.h>

/*

This class is meant to analyze inter-target dependencies globally
during the generation step.  The goal is to produce a set of direct
dependencies for each target such that no cycles are left and the
build order is safe.

For most target types cyclic dependencies are not allowed.  However
36
STATIC libraries may depend on each other in a cyclic fashion.  In
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
general the directed dependency graph forms a directed-acyclic-graph
of strongly connected components.  All strongly connected components
should consist of only STATIC_LIBRARY targets.

In order to safely break dependency cycles we must preserve all other
dependencies passing through the corresponding strongly connected component.
The approach taken by this class is as follows:

  - Collect all targets and form the original dependency graph
  - Run Tarjan's algorithm to extract the strongly connected components
    (error if any member of a non-trivial component is not STATIC)
  - The original dependencies imply a DAG on the components.
    Use the implied DAG to construct a final safe set of dependencies.

The final dependency set is constructed as follows:

  - For each connected component targets are placed in an arbitrary
    order.  Each target depends on the target following it in the order.
    The first target is designated the head and the last target the tail.
    (most components will be just 1 target anyway)

  - Original dependencies between targets in different components are
    converted to connect the depender's component tail to the
    dependee's component head.

In most cases this will reproduce the original dependencies.  However
when there are cycles of static libraries they will be broken in a
safe manner.

For example, consider targets A0, A1, A2, B0, B1, B2, and C with these
dependencies:

  A0 -> A1 -> A2 -> A0  ,  B0 -> B1 -> B2 -> B0 -> A0  ,  C -> B0

Components may be identified as

  Component 0: A0, A1, A2
  Component 1: B0, B1, B2
  Component 2: C

Intra-component dependencies are:

  0: A0 -> A1 -> A2   , head=A0, tail=A2
  1: B0 -> B1 -> B2   , head=B0, tail=B2
  2: head=C, tail=C

The inter-component dependencies are converted as:

  B0 -> A0  is component 1->0 and becomes  B2 -> A0
  C  -> B0  is component 2->1 and becomes  C  -> B0

This leads to the final target dependencies:

  C -> B0 -> B1 -> B2 -> A0 -> A1 -> A2

These produce a safe build order since C depends directly or
transitively on all the static libraries it links.

*/

cmComputeTargetDepends::cmComputeTargetDepends(cmGlobalGenerator* gg)
{
  this->GlobalGenerator = gg;
  cmake* cm = this->GlobalGenerator->GetCMakeInstance();
101
102
103
104
  this->DebugMode = cm->GetState()
                      ->GetGlobalPropertyAsBool("GLOBAL_DEPENDS_DEBUG_MODE");
  this->NoCycles = cm->GetState()
                      ->GetGlobalPropertyAsBool("GLOBAL_DEPENDS_NO_CYCLES");
105
106
107
108
109
110
111
112
113
114
115
116
117
}

cmComputeTargetDepends::~cmComputeTargetDepends()
{
}

bool cmComputeTargetDepends::Compute()
{
  // Build the original graph.
  this->CollectTargets();
  this->CollectDepends();
  if(this->DebugMode)
    {
118
    this->DisplayGraph(this->InitialGraph, "initial");
119
120
121
    }

  // Identify components.
122
  cmComputeComponentGraph ccg(this->InitialGraph);
123
124
  if(this->DebugMode)
    {
125
    this->DisplayComponents(ccg);
126
    }
127
  if(!this->CheckComponents(ccg))
128
129
130
131
132
    {
    return false;
    }

  // Compute the final dependency graph.
133
134
135
136
  if(!this->ComputeFinalDepends(ccg))
    {
    return false;
    }
137
138
  if(this->DebugMode)
    {
139
    this->DisplayGraph(this->FinalGraph, "final");
140
141
142
143
144
145
    }

  return true;
}

void
146
cmComputeTargetDepends::GetTargetDirectDepends(cmGeneratorTarget const* t,
147
                                               cmTargetDependSet& deps)
148
149
150
{
  // Lookup the index for this target.  All targets should be known by
  // this point.
151
  std::map<cmGeneratorTarget const*, int>::const_iterator tii
152
                                                  = this->TargetIndex.find(t);
153
154
155
156
  assert(tii != this->TargetIndex.end());
  int i = tii->second;

  // Get its final dependencies.
157
158
  EdgeList const& nl = this->FinalGraph[i];
  for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
159
    {
160
    cmGeneratorTarget const* dep = this->Targets[*ni];
161
162
    cmTargetDependSet::iterator di = deps.insert(dep).first;
    di->SetType(ni->IsStrong());
163
164
165
166
167
168
169
170
171
172
    }
}

void cmComputeTargetDepends::CollectTargets()
{
  // Collect all targets from all generators.
  std::vector<cmLocalGenerator*> const& lgens =
    this->GlobalGenerator->GetLocalGenerators();
  for(unsigned int i = 0; i < lgens.size(); ++i)
    {
Stephen Kelly's avatar
Stephen Kelly committed
173
174
175
    const std::vector<cmGeneratorTarget*> targets =
        lgens[i]->GetGeneratorTargets();
    for(std::vector<cmGeneratorTarget*>::const_iterator ti = targets.begin();
176
        ti != targets.end(); ++ti)
177
      {
Stephen Kelly's avatar
Stephen Kelly committed
178
      cmGeneratorTarget* gt = *ti;
179
      int index = static_cast<int>(this->Targets.size());
180
181
      this->TargetIndex[gt] = index;
      this->Targets.push_back(gt);
182
183
184
185
186
187
188
      }
    }
}

void cmComputeTargetDepends::CollectDepends()
{
  // Allocate the dependency graph adjacency lists.
189
  this->InitialGraph.resize(this->Targets.size());
190
191
192
193
194
195
196
197
198
199
200

  // Compute each dependency list.
  for(unsigned int i=0; i < this->Targets.size(); ++i)
    {
    this->CollectTargetDepends(i);
    }
}

void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
{
  // Get the depender.
201
  cmGeneratorTarget const* depender = this->Targets[depender_index];
202
  if (depender->GetType() == cmState::INTERFACE_LIBRARY)
203
204
205
    {
    return;
    }
206

207
208
209
210
  // Loop over all targets linked directly in all configs.
  // We need to make targets depend on the union of all config-specific
  // dependencies in all targets, because the generated build-systems can't
  // deal with config-specific dependencies.
211
  {
212
  std::set<std::string> emitted;
213

214
  std::vector<std::string> configs;
215
  depender->Makefile->GetConfigurations(configs);
216
217
218
219
  if (configs.empty())
    {
    configs.push_back("");
    }
220
221
222
  for (std::vector<std::string>::const_iterator it = configs.begin();
    it != configs.end(); ++it)
    {
223
    std::vector<cmSourceFile const*> objectFiles;
224
    depender->GetExternalObjects(objectFiles, *it);
225
226
227
228
229
230
    for(std::vector<cmSourceFile const*>::const_iterator
        oi = objectFiles.begin(); oi != objectFiles.end(); ++oi)
      {
      std::string objLib = (*oi)->GetObjectLibrary();
      if (!objLib.empty() && emitted.insert(objLib).second)
        {
231
232
233
234
        if(depender->GetType() != cmState::EXECUTABLE &&
            depender->GetType() != cmState::STATIC_LIBRARY &&
            depender->GetType() != cmState::SHARED_LIBRARY &&
            depender->GetType() != cmState::MODULE_LIBRARY)
235
236
237
238
239
          {
          this->GlobalGenerator->GetCMakeInstance()
            ->IssueMessage(cmake::FATAL_ERROR,
                            "Only executables and non-OBJECT libraries may "
                            "reference target objects.",
240
                            depender->GetBacktrace());
241
242
          return;
          }
243
        const_cast<cmGeneratorTarget*>(depender)->Target->AddUtility(objLib);
244
245
        }
      }
246

247
    cmLinkImplementation const* impl = depender->GetLinkImplementation(*it);
248

249
250
    // A target should not depend on itself.
    emitted.insert(depender->GetName());
251
    for(std::vector<cmLinkImplItem>::const_iterator
252
253
          lib = impl->Libraries.begin();
        lib != impl->Libraries.end(); ++lib)
254
255
256
257
      {
      // Don't emit the same library twice for this target.
      if(emitted.insert(*lib).second)
        {
Stephen Kelly's avatar
Stephen Kelly committed
258
        this->AddTargetDepend(depender_index, *lib, true);
259
        this->AddInterfaceDepends(depender_index, *lib, emitted);
260
261
262
263
        }
      }
    }
  }
264
265

  // Loop over all utility dependencies.
266
  {
267
  std::set<cmLinkItem> const& tutils = depender->GetUtilityItems();
268
  std::set<std::string> emitted;
269
270
  // A target should not depend on itself.
  emitted.insert(depender->GetName());
271
  for(std::set<cmLinkItem>::const_iterator util = tutils.begin();
272
273
274
275
276
      util != tutils.end(); ++util)
    {
    // Don't emit the same utility twice for this target.
    if(emitted.insert(*util).second)
      {
Stephen Kelly's avatar
Stephen Kelly committed
277
      this->AddTargetDepend(depender_index, *util, false);
278
279
      }
    }
280
  }
281
282
}

283
void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
284
285
286
                                             const cmGeneratorTarget* dependee,
                                             const std::string& config,
                                             std::set<std::string> &emitted)
287
{
288
  cmGeneratorTarget const* depender = this->Targets[depender_index];
289
  if(cmLinkInterface const* iface =
290
                                dependee->GetLinkInterface(config,
291
                                                           depender))
292
    {
293
    for(std::vector<cmLinkItem>::const_iterator
294
295
296
297
298
299
        lib = iface->Libraries.begin();
        lib != iface->Libraries.end(); ++lib)
      {
      // Don't emit the same library twice for this target.
      if(emitted.insert(*lib).second)
        {
Stephen Kelly's avatar
Stephen Kelly committed
300
        this->AddTargetDepend(depender_index, *lib, true);
301
        this->AddInterfaceDepends(depender_index, *lib, emitted);
302
303
304
305
306
307
        }
      }
    }
}

void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
308
                                             cmLinkItem const& dependee_name,
309
                                             std::set<std::string> &emitted)
310
{
311
  cmGeneratorTarget const* depender = this->Targets[depender_index];
312
  cmGeneratorTarget const* dependee = dependee_name.Target;
313
314
315
  // Skip targets that will not really be linked.  This is probably a
  // name conflict between an external library and an executable
  // within the project.
316
  if(dependee &&
317
     dependee->GetType() == cmState::EXECUTABLE &&
318
     !dependee->IsExecutableWithExports())
319
320
321
322
323
324
    {
    dependee = 0;
    }

  if(dependee)
    {
325
    this->AddInterfaceDepends(depender_index, dependee, "", emitted);
326
    std::vector<std::string> configs;
327
    depender->Makefile->GetConfigurations(configs);
328
329
330
331
332
    for (std::vector<std::string>::const_iterator it = configs.begin();
      it != configs.end(); ++it)
      {
      // A target should not depend on itself.
      emitted.insert(depender->GetName());
333
      this->AddInterfaceDepends(depender_index, dependee, *it, emitted);
334
335
336
337
      }
    }
}

338
339
340
void cmComputeTargetDepends::AddTargetDepend(
  int depender_index, cmLinkItem const& dependee_name,
  bool linking)
341
342
{
  // Get the depender.
343
  cmGeneratorTarget const* depender = this->Targets[depender_index];
344
345

  // Check the target's makefile first.
346
  cmGeneratorTarget const* dependee = dependee_name.Target;
347

348
  if(!dependee && !linking &&
349
    (depender->GetType() != cmState::GLOBAL_TARGET))
350
351
352
    {
    cmake::MessageType messageType = cmake::AUTHOR_WARNING;
    bool issueMessage = false;
353
    std::ostringstream e;
354
    switch(depender->GetPolicyStatusCMP0046())
355
356
      {
      case cmPolicies::WARN:
Stephen Kelly's avatar
Stephen Kelly committed
357
        e << cmPolicies::GetPolicyWarning(cmPolicies::CMP0046) << "\n";
358
359
360
361
362
363
364
365
366
367
368
369
        issueMessage = true;
      case cmPolicies::OLD:
        break;
      case cmPolicies::NEW:
      case cmPolicies::REQUIRED_IF_USED:
      case cmPolicies::REQUIRED_ALWAYS:
        issueMessage = true;
        messageType = cmake::FATAL_ERROR;
      }
    if(issueMessage)
      {
      cmake* cm = this->GlobalGenerator->GetCMakeInstance();
370

371
372
373
374
      e << "The dependency target \"" <<  dependee_name
        << "\" of target \"" << depender->GetName() << "\" does not exist.";

      cmListFileBacktrace const* backtrace =
375
        depender->GetUtilityBacktrace(dependee_name);
376
      if(backtrace)
377
        {
378
379
380
381
382
        cm->IssueMessage(messageType, e.str(), *backtrace);
        }
      else
        {
        cm->IssueMessage(messageType, e.str());
383
384
385
386
387
        }

      }
    }

388
389
390
391
  // Skip targets that will not really be linked.  This is probably a
  // name conflict between an external library and an executable
  // within the project.
  if(linking && dependee &&
392
     dependee->GetType() == cmState::EXECUTABLE &&
393
     !dependee->IsExecutableWithExports())
394
395
396
397
    {
    dependee = 0;
    }

398
  if(dependee)
399
    {
400
    this->AddTargetDepend(depender_index, dependee, linking);
401
    }
402
}
403

404
void cmComputeTargetDepends::AddTargetDepend(int depender_index,
405
                                             const cmGeneratorTarget* dependee,
406
407
                                             bool linking)
{
408
  if(dependee->IsImported() ||
409
     dependee->GetType() == cmState::INTERFACE_LIBRARY)
410
    {
411
412
    // Skip IMPORTED and INTERFACE targets but follow their utility
    // dependencies.
413
    std::set<cmLinkItem> const& utils = dependee->GetUtilityItems();
414
    for(std::set<cmLinkItem>::const_iterator i = utils.begin();
415
416
        i != utils.end(); ++i)
      {
417
      if(cmGeneratorTarget const* transitive_dependee = i->Target)
418
        {
419
        this->AddTargetDepend(depender_index, transitive_dependee, false);
420
        }
421
422
423
424
425
426
      }
    }
  else
    {
    // Lookup the index for this target.  All targets should be known by
    // this point.
427
    std::map<cmGeneratorTarget const*, int>::const_iterator tii =
428
429
430
431
432
433
434
435
      this->TargetIndex.find(dependee);
    assert(tii != this->TargetIndex.end());
    int dependee_index = tii->second;

    // Add this entry to the dependency graph.
    this->InitialGraph[depender_index].push_back(
      cmGraphEdge(dependee_index, !linking));
    }
436
437
438
}

void
439
440
cmComputeTargetDepends::DisplayGraph(Graph const& graph,
                                     const std::string& name)
441
{
442
  fprintf(stderr, "The %s target dependency graph is:\n", name.c_str());
443
444
445
  int n = static_cast<int>(graph.size());
  for(int depender_index = 0; depender_index < n; ++depender_index)
    {
446
    EdgeList const& nl = graph[depender_index];
447
    cmGeneratorTarget const* depender = this->Targets[depender_index];
448
    fprintf(stderr, "target %d is [%s]\n",
449
            depender_index, depender->GetName().c_str());
450
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
451
      {
452
      int dependee_index = *ni;
453
      cmGeneratorTarget const* dependee = this->Targets[dependee_index];
454
      fprintf(stderr, "  depends on target %d [%s] (%s)\n", dependee_index,
455
              dependee->GetName().c_str(), ni->IsStrong()? "strong" : "weak");
456
457
458
459
460
      }
    }
  fprintf(stderr, "\n");
}

461
462
463
void
cmComputeTargetDepends
::DisplayComponents(cmComputeComponentGraph const& ccg)
464
465
{
  fprintf(stderr, "The strongly connected components are:\n");
466
467
  std::vector<NodeList> const& components = ccg.GetComponents();
  int n = static_cast<int>(components.size());
468
469
  for(int c = 0; c < n; ++c)
    {
470
    NodeList const& nl = components[c];
471
    fprintf(stderr, "Component (%d):\n", c);
472
    for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
473
      {
474
      int i = *ni;
475
      fprintf(stderr, "  contains target %d [%s]\n",
476
              i, this->Targets[i]->GetName().c_str());
477
478
479
480
481
      }
    }
  fprintf(stderr, "\n");
}

482
483
484
bool
cmComputeTargetDepends
::CheckComponents(cmComputeComponentGraph const& ccg)
485
486
487
{
  // All non-trivial components should consist only of static
  // libraries.
488
489
  std::vector<NodeList> const& components = ccg.GetComponents();
  int nc = static_cast<int>(components.size());
490
491
492
  for(int c=0; c < nc; ++c)
    {
    // Get the current component.
493
    NodeList const& nl = components[c];
494
495

    // Skip trivial components.
496
    if(nl.size() < 2)
497
498
499
500
      {
      continue;
      }

501
502
503
504
505
506
507
    // Immediately complain if no cycles are allowed at all.
    if(this->NoCycles)
      {
      this->ComplainAboutBadComponent(ccg, c);
      return false;
      }

508
    // Make sure the component is all STATIC_LIBRARY targets.
509
    for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
510
      {
511
      if(this->Targets[*ni]->GetType() != cmState::STATIC_LIBRARY)
512
        {
513
        this->ComplainAboutBadComponent(ccg, c);
514
515
516
517
518
519
520
521
        return false;
        }
      }
    }
  return true;
}

void
522
cmComputeTargetDepends
523
524
::ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c,
                            bool strong)
525
526
{
  // Construct the error message.
527
  std::ostringstream e;
528
529
  e << "The inter-target dependency graph contains the following "
    << "strongly connected component (cycle):\n";
530
531
532
533
  std::vector<NodeList> const& components = ccg.GetComponents();
  std::vector<int> const& cmap = ccg.GetComponentMap();
  NodeList const& cl = components[c];
  for(NodeList::const_iterator ci = cl.begin(); ci != cl.end(); ++ci)
534
535
536
    {
    // Get the depender.
    int i = *ci;
537
    cmGeneratorTarget const* depender = this->Targets[i];
538
539

    // Describe the depender.
540
    e << "  \"" << depender->GetName() << "\" of type "
541
      << cmState::GetTargetTypeName(depender->GetType()) << "\n";
542
543

    // List its dependencies that are inside the component.
544
545
    EdgeList const& nl = this->InitialGraph[i];
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
546
      {
547
548
      int j = *ni;
      if(cmap[j] == c)
549
        {
550
        cmGeneratorTarget const* dependee = this->Targets[j];
551
552
        e << "    depends on \"" << dependee->GetName() << "\""
          << " (" << (ni->IsStrong()? "strong" : "weak") << ")\n";
553
554
555
        }
      }
    }
556
557
558
559
560
561
562
563
564
  if(strong)
    {
    // Custom command executable dependencies cannot occur within a
    // component of static libraries.  The cycle must appear in calls
    // to add_dependencies.
    e << "The component contains at least one cycle consisting of strong "
      << "dependencies (created by add_dependencies) that cannot be broken.";
    }
  else if(this->NoCycles)
565
566
567
568
569
570
571
572
573
    {
    e << "The GLOBAL_DEPENDS_NO_CYCLES global property is enabled, so "
      << "cyclic dependencies are not allowed even among static libraries.";
    }
  else
    {
    e << "At least one of these targets is not a STATIC_LIBRARY.  "
      << "Cyclic dependencies are allowed only among static libraries.";
    }
574
575
576
  cmSystemTools::Error(e.str().c_str());
}

577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
bool
cmComputeTargetDepends
::IntraComponent(std::vector<int> const& cmap, int c, int i, int* head,
                 std::set<int>& emitted, std::set<int>& visited)
{
  if(!visited.insert(i).second)
    {
    // Cycle in utility depends!
    return false;
    }
  if(emitted.insert(i).second)
    {
    // Honor strong intra-component edges in the final order.
    EdgeList const& el = this->InitialGraph[i];
    for(EdgeList::const_iterator ei = el.begin(); ei != el.end(); ++ei)
      {
      int j = *ei;
      if(cmap[j] == c && ei->IsStrong())
        {
596
        this->FinalGraph[i].push_back(cmGraphEdge(j, true));
597
598
599
600
601
602
603
604
605
606
        if(!this->IntraComponent(cmap, c, j, head, emitted, visited))
          {
          return false;
          }
        }
      }

    // Prepend to a linear linked-list of intra-component edges.
    if(*head >= 0)
      {
607
      this->FinalGraph[i].push_back(cmGraphEdge(*head, false));
608
609
610
611
612
613
614
615
616
617
618
      }
    else
      {
      this->ComponentTail[c] = i;
      }
    *head = i;
    }
  return true;
}

bool
619
620
cmComputeTargetDepends
::ComputeFinalDepends(cmComputeComponentGraph const& ccg)
621
{
622
623
624
625
626
627
628
  // Get the component graph information.
  std::vector<NodeList> const& components = ccg.GetComponents();
  Graph const& cgraph = ccg.GetComponentGraph();

  // Allocate the final graph.
  this->FinalGraph.resize(0);
  this->FinalGraph.resize(this->InitialGraph.size());
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
  // Choose intra-component edges to linearize dependencies.
  std::vector<int> const& cmap = ccg.GetComponentMap();
  this->ComponentHead.resize(components.size());
  this->ComponentTail.resize(components.size());
  int nc = static_cast<int>(components.size());
  for(int c=0; c < nc; ++c)
    {
    int head = -1;
    std::set<int> emitted;
    NodeList const& nl = components[c];
    for(NodeList::const_reverse_iterator ni = nl.rbegin();
        ni != nl.rend(); ++ni)
      {
      std::set<int> visited;
      if(!this->IntraComponent(cmap, c, *ni, &head, emitted, visited))
        {
        // Cycle in add_dependencies within component!
        this->ComplainAboutBadComponent(ccg, c, true);
        return false;
        }
      }
    this->ComponentHead[c] = head;
    }

654
  // Convert inter-component edges to connect component tails to heads.
655
656
  int n = static_cast<int>(cgraph.size());
  for(int depender_component=0; depender_component < n; ++depender_component)
657
    {
658
    int depender_component_tail = this->ComponentTail[depender_component];
659
660
    EdgeList const& nl = cgraph[depender_component];
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
661
      {
662
      int dependee_component = *ni;
663
      int dependee_component_head = this->ComponentHead[dependee_component];
664
      this->FinalGraph[depender_component_tail]
665
        .push_back(cmGraphEdge(dependee_component_head, ni->IsStrong()));
666
667
      }
    }
668
  return true;
669
}