Class: Lyp::DependencyResolver

Inherits:
Object
  • Object
show all
Defined in:
lib/lyp/resolver.rb

Constant Summary collapse

DEP_RE = 
/\\(require|include|pinclude|pincludeOnce) "([^"]+)"/.freeze
INCLUDE = 
"include".freeze
PINCLUDE = 
"pinclude".freeze
PINCLUDE_ONCE = 
"pincludeOnce".freeze
REQUIRE = 
"require".freeze
MAIN_PACKAGE_FILE = 
'package.ly'

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tree, opts = {}) ⇒ DependencyResolver

Returns a new instance of DependencyResolver.



63
64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/lyp/resolver.rb', line 63

def initialize(tree, opts = {})
  if tree.is_a?(String)
    @user_file = tree
    @tree = DependencyLeaf.new
  else
    @tree = tree
  end
  @opts = opts
  @ext_require = @opts[:ext_require]
  @queue = []
  @processed_files = {}
end

Instance Attribute Details

#opts ⇒ Object (readonly)

Returns the value of attribute opts.



61
62
63
 
# File 'lib/lyp/resolver.rb', line 61

def opts
  @opts
end

#tree ⇒ Object (readonly)

Returns the value of attribute tree.



61
62
63
 
# File 'lib/lyp/resolver.rb', line 61

def tree
  @tree
end

Class Method Details

.error(msg, location = nil) ⇒ Object

Raises:



559
560
561
562
 
# File 'lib/lyp/resolver.rb', line 559

def self.error(msg, location = nil)
  location = location ? format_location(location) : nil
  raise ResolveError, msg % location
end

.format_location(location) ⇒ Object 



564
565
566
567
568
569
 
# File 'lib/lyp/resolver.rb', line 564

def self.format_location(location)
  return "" unless location
  return "require flag" if location[:ext_require]
  source_line = get_source_line(location[:path], location[:line])
  "#{location[:path]}:#{location[:line]}: \n\n  #{source_line}\n"
end

.get_source_line(path, line) ⇒ Object 



571
572
573
574
575
 
# File 'lib/lyp/resolver.rb', line 571

def self.get_source_line(path, line)
  IO.read(path).lines[line - 1]
rescue => e
  "???"
end

Instance Method Details

#available_packages ⇒ Object

Memoize and return a hash of available packages



391
392
393
 
# File 'lib/lyp/resolver.rb', line 391

def available_packages
  @available_packages ||= get_available_packages(Lyp.packages_dir)
end

#compile_dependency_tree(opts = {}) ⇒ Object

Each “leaf” on the dependency tree is a hash of the following structure: 

dependencies: {
  "<package_name>" => {
    clause: "<package>@<version_specifier>",
    versions: {
      "<version>" => {...
      ...
    }
  }
}

}

Since files to be processed are added to a queue, this method loops through the queue until it’s empty.



144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
 
# File 'lib/lyp/resolver.rb', line 144

def compile_dependency_tree(opts = {})
  old_opts = @opts
  @opts = @opts.merge(opts)
  @queue = []
  @processed_files = {}
  @tree ||= DependencyLeaf.new

  queue_file_for_processing(@user_file, @tree)

  while job = pull_file_from_queue
    process_lilypond_file(job[:path], job[:leaf], opts)
  end

  unless @opts[:ignore_missing]
    squash_old_versions
    remove_unfulfilled_dependencies(tree)
  end

  @tree
ensure
  @opts = old_opts
end

#dependencies_array(leaf, processed = {}) ⇒ Object

Converts a simplified dependency tree into an array of dependencies, containing a sub-array for each top-level dependency. Each such sub-array contains, in its turn, version permutations for the top-level dependency and any transitive dependencies.



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
 
# File 'lib/lyp/resolver.rb', line 300

def dependencies_array(leaf, processed = {})
  return processed[leaf] if processed[leaf]

  deps_array = []
  processed[leaf] = deps_array

  leaf.each do |pack, versions|
    a = []
    versions.each do |version, deps|
      perms = []
      sub_perms = dependencies_array(deps, processed)
      if sub_perms == []
        perms += [version]
      else
        sub_perms[0].each do |perm|
          perms << [version] + [perm].flatten
        end
      end
      a += perms
    end
    deps_array << a
  end

  deps_array
end

#error(msg, location = nil) ⇒ Object 



555
556
557
 
# File 'lib/lyp/resolver.rb', line 555

def error(msg, location = nil)
  DependencyResolver.error(msg, location)
end

#filter_invalid_permutations(permutations) ⇒ Object

Remove invalid permutations, that is permutations that contain multiple versions of the same package, a scenario which could arrive in the case of circular dependencies, or when different dependencies rely on different versions of the same transitive dependency.



330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
 
# File 'lib/lyp/resolver.rb', line 330

def filter_invalid_permutations(permutations)
  valid = []
  permutations.each do |perm|
    versions = {}; invalid = false
    perm.each do |ref|
      if ref =~ /(.+)@(.+)/
        name, version = $1, $2
        if versions[name] && versions[name] != version
          invalid = true
          break
        else
          versions[name] = version
        end
      end
    end
    valid << perm.uniq unless invalid
  end

  valid
end

#find_matching_packages(req) ⇒ Object

Find packages meeting the version requirement



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
 
# File 'lib/lyp/resolver.rb', line 418

def find_matching_packages(req)
  return {} unless req =~ Lyp::PACKAGE_RE

  req_package = $1
  req_version = $2

  req = nil
  if @opts[:forced_package_paths] && @opts[:forced_package_paths][req_package]
    req_version = 'forced'
  end

  req = Lyp.version_req(req_version || '>=0') rescue nil
  available_packages.select do |package, leaf|
    if (package =~ Lyp::PACKAGE_RE) && (req_package == $1)
      version = Lyp.version($2 || '0') rescue nil
      if version.nil? || req.nil?
        req_version.nil? || (req_version == $2)
      else
        req =~ version
      end
    else
      nil
    end
  end
end

#find_package_versions(ref, leaf, location) ⇒ Object

Find available packaging matching the package specifier, and queue them for processing any include files or transitive dependencies.



446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
 
# File 'lib/lyp/resolver.rb', line 446

def find_package_versions(ref, leaf, location)
  return {} unless ref =~ Lyp::PACKAGE_RE
  ref_package = $1
  version_clause = $2

  matches = find_matching_packages(ref)

  # Raise if no match found and we're at top of the tree
  if matches.empty? && (leaf == tree) && !opts[:ignore_missing]
    msg = "Missing package dependency #{ref} in %sYou can install any missing packages by running:\n\n  lyp resolve #{@user_file}"
    error(msg, location)
  end

  matches.each do |p, package_leaf|
    if package_leaf.path
      queue_file_for_processing(package_leaf.path, package_leaf)
    end
  end

  # Setup up dependency leaf
  leaf.add_dependency(ref_package, DependencySpec.new(ref, matches, location))
end

#get_available_packages(dir) ⇒ Object

Return a hash of all packages found in the packages directory, creating a leaf for each package



399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
 
# File 'lib/lyp/resolver.rb', line 399

def get_available_packages(dir)
  packages = Dir["#{Lyp.packages_dir}/*"].inject({}) do |m, p|
    name = File.basename(p)
    m[name] = DependencyPackage.new(File.join(p, MAIN_PACKAGE_FILE))
    m
  end

  forced_paths = @opts[:forced_package_paths] || {}

  if @opts[:forced_package_paths]
    @opts[:forced_package_paths].each do |package, path|
      packages["#{package}@forced"] = DependencyPackage.new(File.join(path, MAIN_PACKAGE_FILE))
    end
  end

  packages
end

#map_specifiers_to_versions ⇒ Object

Return a hash mapping packages to package specifiers to spec objects, to be used to eliminate older versions from the dependency tree



499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
 
# File 'lib/lyp/resolver.rb', line 499

def map_specifiers_to_versions
  specifiers = {}
  processed = {}

  l = lambda do |t|
    return if processed[t.object_id]
    processed[t.object_id] = true
    t.dependencies.each do |package, spec|
      specifiers[package] ||= {}
      specifiers[package][spec.clause] ||= []
      specifiers[package][spec.clause] << spec
      spec.versions.each_value {|v| l[v]}
    end
  end

  l[@tree]
  specifiers
end

#permutate_simplified_tree ⇒ Object

Create permutations of package versions for the given dependency tree. The tree is first simplified (superfluous information removed), then turned into an array of dependencies, from which version permutations are generated.



258
259
260
261
262
263
264
 
# File 'lib/lyp/resolver.rb', line 258

def permutate_simplified_tree
  deps = dependencies_array(simplified_deps_tree(tree))
  return deps if deps.empty?

  # Return a cartesian product of dependencies
  deps[0].product(*deps[1..-1]).map(&:flatten)
end

#process_include_command(ref, dir, leaf, opts, location) ⇒ Object 



207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
 
# File 'lib/lyp/resolver.rb', line 207

def process_include_command(ref, dir, leaf, opts, location)
  # a package would normally use a plain \pinclude or \pincludeOnce
  # command to include package files, e.g. \pinclude "inc/init.ly".
  #
  # But a package can also qualify the file reference with the package
  # name, in order to be able to load files after the package has already
  # been loaded, e.g. \pinclude "mypack:inc/init.ly"
  if ref =~ /^([^\:]+)\:(.+)$/
    # ignore null package (used for testing purposes only)
    return if $1 == 'null'
    ref = $2
  end
  qualified_path = File.expand_path(ref, dir)

  unless File.file?(qualified_path)
    error("Invalid include file specified in %s", location)
  end

  queue_file_for_processing(qualified_path, leaf)
end

#process_lilypond_file(path, leaf, opts) ⇒ Object

Scans a lilypond file for require and (p)include statements. An included file is queued for processing. For required packages, search for suitable versions of the package and add them to the tree.

The leaf argument is a pointer to the current leaf on the tree on which to add dependencies. This is how transitive dependencies are represented.



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
 
# File 'lib/lyp/resolver.rb', line 173

def process_lilypond_file(path, leaf, opts)
  # path is expected to be absolute
  return if @processed_files[path]

  ly_content = IO.read(path)
  dir = File.dirname(path)

  # Parse lilypond file for \include and \require
  location = {path: path, line: 0}
  ly_content.each_line do |line|
    location[:line] += 1
    line.scan(DEP_RE) do |type, ref|
      case type
      when INCLUDE, PINCLUDE, PINCLUDE_ONCE
        process_include_command(ref, dir, leaf, opts, location)
      when REQUIRE
        process_require_command(ref, dir, leaf, opts, location)
      end
    end
  end

  # process any external requires (supplied using the -r command line option)
  if @ext_require
    @ext_require.each do |p|
      process_require_command(p, dir, leaf, opts, {ext_require: true})
    end
    @ext_require = nil
  end

  @processed_files[path] = true
rescue Errno::ENOENT
  error("Could not find file #{path}")
end

#process_require_command(ref, dir, leaf, opts, location) ⇒ Object 



228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
 
# File 'lib/lyp/resolver.rb', line 228

def process_require_command(ref, dir, leaf, opts, location)
  forced_path = nil
  if ref =~ /^([^\:]+)\:(.+)$/
    ref = $1
    forced_path = File.expand_path($2, dir)
  end

  ref =~ Lyp::PACKAGE_RE
  package, version = $1, $2
  return if package == 'null'

  # set forced path if applicable
  if forced_path
    set_forced_package_path(package, forced_path)
  end

  find_package_versions(ref, leaf, location)
end

#pull_file_from_queue ⇒ Object 



251
252
253
 
# File 'lib/lyp/resolver.rb', line 251

def pull_file_from_queue
  @queue.shift
end

#queue_file_for_processing(path, leaf) ⇒ Object 



247
248
249
 
# File 'lib/lyp/resolver.rb', line 247

def queue_file_for_processing(path, leaf)
  @queue << {path: path, leaf: leaf}
end

#remove_unfulfilled_dependencies(leaf, raise_on_missing = true, processed = {}) ⇒ Object

Recursively remove any dependency for which no version is locally available. If no version is found for any of the dependencies specified by the user, an error is raised.

The processed hash is used for keeping track of dependencies that were already processed, and thus deal with circular dependencies.



524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
 
# File 'lib/lyp/resolver.rb', line 524

def remove_unfulfilled_dependencies(leaf, raise_on_missing = true, processed = {})
  tree.dependencies.each do |package, dependency|
    dependency.versions.select! do |version, leaf|
      if processed[version]
        true
      else
        processed[version] = true

        # Remove unfulfilled transitive dependencies
        remove_unfulfilled_dependencies(leaf, false, processed)
        valid = true
        leaf.dependencies.each do |k, v|
          valid = false if v.versions.empty?
        end
        valid
      end
    end
    if dependency.versions.empty? && raise_on_missing
      error("No valid version found for package #{package}")
    end
  end
end

#resolve_package_dependencies ⇒ Object

Resolving package dependencies involves two stages:

  1. Create a dependency tree from user files and packages

  2. Resolve the dependency tree into a list of specific package versions



79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/lyp/resolver.rb', line 79

def resolve_package_dependencies
  compile_dependency_tree
  definite_versions = resolve_tree
  specifier_map = map_specifiers_to_versions

  refs, dirs = {}, {}
  definite_versions.each do |v|
    package = v =~ Lyp::PACKAGE_RE && $1

    specifier_map[package].each_key {|s| refs[s] = package}
    dirs[package] = File.dirname(available_packages[v].path)
  end

  {
    user_file: @user_file,
    definite_versions: definite_versions,
    package_refs: refs,
    package_dirs: dirs,
    preload: @opts[:ext_require]
  }
end

#resolve_tree ⇒ Object

Resolve the given dependency tree and return a list of concrete packages that meet all dependency requirements.

The following stages are involved:

  • Create permutations of possible version combinations for all dependencies

  • Remove invalid permutations

  • Select the permutation with the highest versions



108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/lyp/resolver.rb', line 108

def resolve_tree
  permutations = permutate_simplified_tree
  permutations = filter_invalid_permutations(permutations)

  # select highest versioned dependencies (for those specified by user)
  user_deps = tree.dependencies.keys
  result = select_highest_versioned_permutation(permutations, user_deps).flatten

  if result.empty? && !tree.dependencies.empty?
    error("Failed to satisfy dependency requirements")
  else
    result
  end
end

#select_highest_versioned_permutation(permutations, user_deps) ⇒ Object

Select the highest versioned permutation of package versions



352
353
354
355
 
# File 'lib/lyp/resolver.rb', line 352

def select_highest_versioned_permutation(permutations, user_deps)
  sorted = sort_permutations(permutations, user_deps)
  sorted.empty? ? [] : sorted.last
end

#set_forced_package_path(package, path) ⇒ Object 



547
548
549
550
551
552
553
 
# File 'lib/lyp/resolver.rb', line 547

def set_forced_package_path(package, path)
  @opts[:forced_package_paths] ||= {}
  @opts[:forced_package_paths][package] = path

  available_packages["#{package}@forced"] = DependencyPackage.new(
    File.join(path, MAIN_PACKAGE_FILE))
end

#simplified_deps_tree(leaf, processed = {}) ⇒ Object

Converts the dependency tree into a simplified dependency tree of the form 

<package name> =>
  <version> =>
    <package name> =>
      <version> => ...
      ...
    ...
  ...
...

The processed hash is used to deal with circular dependencies



278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
 
# File 'lib/lyp/resolver.rb', line 278

def simplified_deps_tree(leaf, processed = {})
  return {} unless leaf.dependencies

  return processed[leaf] if processed[leaf]
  processed[leaf] = dep_versions = {}

  # For each dependency, generate a deps tree for each available version
  leaf.dependencies.each do |p, spec|
    dep_versions[p] = {}
    spec.versions.each do |v, subleaf|
      dep_versions[p][v] =
        simplified_deps_tree(subleaf, processed)
    end
  end

  dep_versions
end

#sort_permutations(permutations, user_deps) ⇒ Object

Sort permutations by version numbers



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
 
# File 'lib/lyp/resolver.rb', line 358

def sort_permutations(permutations, user_deps)
  # Cache for versions converted to Gem::Version instances
  versions = {}

  map = lambda do |m, p|
    if p =~ Lyp::PACKAGE_RE
      m[$1] = versions[p] ||= (Lyp.version($2 || '0.0') rescue nil)
    end
    m
  end

  compare = lambda do |x, y|
    x_versions = x.inject({}, &map)
    y_versions = y.inject({}, &map)

    # If the dependency is direct (not transitive), just compare its versions.
    # Otherwise, add the result of comparison to score.
    x_versions.inject(0) do |score, kv|
      package = kv[0]
      cmp = kv[1] <=> y_versions[package]
      if user_deps.include?(package) && cmp != 0
        return cmp
      else
        score += cmp unless cmp.nil?
      end
      score
    end
  end

  permutations.sort(&compare)
end

#squash_old_versions ⇒ Object

Remove redundant older versions of dependencies by collating package versions by package specifiers, then removing older versions for any package for which a single package specifier exists.



472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
 
# File 'lib/lyp/resolver.rb', line 472

def squash_old_versions
  specifiers = map_specifiers_to_versions

  compare_versions = lambda do |x, y|
    v_x = x =~ Lyp::PACKAGE_RE && Lyp.version($2)
    v_y = y =~ Lyp::PACKAGE_RE && Lyp.version($2)
    x <=> y
  end

  specifiers.each do |package, clauses|
    # Remove old versions only if the package is referenced using a single
    # specifier clause
    next unless clauses.size == 1

    specs = clauses.values.first
    specs.each do |s|
      if s.versions.values.uniq.size == 1
        versions = s.versions.keys.sort(&compare_versions)
        latest = versions.last
        s.versions.select! {|k, v| k == latest}
      end
    end
  end
end