Class: Lyp::Resolver

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 Method Summary collapse

Constructor Details

#initialize(user_file, opts = {}) ⇒ Resolver

Returns a new instance of Resolver.



2
3
4
5
 
# File 'lib/lyp/resolver.rb', line 2

def initialize(user_file, opts = {})
  @user_file = user_file
  @opts = opts
end

Instance Method Details

#available_packages(tree) ⇒ Object

Memoize and return a hash of available packages



196
197
198
 
# File 'lib/lyp/resolver.rb', line 196

def available_packages(tree)
  tree[:available_packages] ||= get_available_packages(Lyp.packages_dir)
end

#dependencies_array(tree, 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.



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

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

  deps_array = []
  processed[tree] = deps_array
  
  tree.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

#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.



421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
 
# File 'lib/lyp/resolver.rb', line 421

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, tree) ⇒ Object

Find packages meeting the version requirement



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

def find_matching_packages(req, tree)
  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 = Gem::Requirement.new(req_version || '>=0') rescue nil
  available_packages(tree).select do |package, sub_tree|
    if (package =~ Lyp::PACKAGE_RE) && (req_package == $1)
      version = Gem::Version.new($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, tree, leaf, opts) ⇒ Object

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



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

def find_package_versions(ref, tree, leaf, opts)
  return {} unless ref =~ Lyp::PACKAGE_RE
  ref_package = $1
  version_clause = $2
  
  matches = find_matching_packages(ref, tree)
  
  # Raise if no match found and we're at top of the tree
  if matches.empty? && (tree == leaf) && !opts[:ignore_missing]
    raise "No package found for requirement #{ref}"
  end
  
  matches.each do |p, subtree|
    if subtree[:path]
      queue_file_for_processing(subtree[:path], tree, subtree)
    end
  end

  # Setup up dependency leaf
  (leaf[:dependencies] ||= {}).merge!({
    ref_package => {
      clause: ref,
      versions: matches
    }
  })
end

#get_available_packages(dir) ⇒ Object

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



212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
 
# File 'lib/lyp/resolver.rb', line 212

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

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

#get_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.



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/lyp/resolver.rb', line 53

def get_dependency_tree(opts = {})
  tree = {
    dependencies: {},
    queue: [],
    processed_files: {}
  }
  
  queue_file_for_processing(@user_file, tree, tree)

  while job = pull_file_from_queue(tree)
    process_lilypond_file(job[:path], tree, job[:leaf], opts)
  end
  
  unless opts[:ignore_missing]
    squash_old_versions(tree)
    remove_unfulfilled_dependencies(tree)
  end
  
  tree
end

#map_specifiers_to_versions(tree) ⇒ Object

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



302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
 
# File 'lib/lyp/resolver.rb', line 302

def map_specifiers_to_versions(tree)
  specifiers = {}
  processed = {}
  
  l = lambda do |t|
    return if processed[t]
    processed[t] = true
    t[:dependencies].each do |package, subtree|
      versions = subtree[:versions]
      clause = subtree[:clause]

      specifiers[package] ||= {}
      specifiers[package][clause] ||= []
      specifiers[package][clause] << versions
      
      versions.each_value {|v| l[v]}
    end
  end
  
  l[tree]
  specifiers
end

#permutate_simplified_tree(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.



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

def permutate_simplified_tree(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_lilypond_file(path, tree, 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.



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

def process_lilypond_file(path, tree, leaf, opts)
  # path is expected to be absolute
  return if tree[:processed_files][path]
  
  ly_content = IO.read(path)
  dir = File.dirname(path)
  
  # Parse lilypond file for \include and \require
  ly_content.scan(DEP_RE) do |type, ref|
    case type
    when INCLUDE, PINCLUDE, PINCLUDE_ONCE
      # 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)
        next if $1 == 'null'
        ref = $2
      end
      qualified_path = File.expand_path(ref, dir)
      queue_file_for_processing(qualified_path, tree, leaf)
    when REQUIRE
      forced_path = nil
      if ref =~ /^([^\:]+)\:(.+)$/
        ref = $1
        forced_path = File.expand_path($2, dir)
      end

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

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

      find_package_versions(ref, tree, leaf, opts)
    end
  end
  
  tree[:processed_files][path] = true
rescue Errno::ENOENT
  raise "Cannot find file #{path}"
end

#pull_file_from_queue(tree) ⇒ Object 



133
134
135
 
# File 'lib/lyp/resolver.rb', line 133

def pull_file_from_queue(tree)
  tree[:queue].shift
end

#queue_file_for_processing(path, tree, leaf) ⇒ Object 



129
130
131
 
# File 'lib/lyp/resolver.rb', line 129

def queue_file_for_processing(path, tree, leaf)
  (tree[:queue] ||= []) << {path: path, leaf: leaf}
end

#remove_unfulfilled_dependencies(tree, 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.



243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
 
# File 'lib/lyp/resolver.rb', line 243

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

        # Remove unfulfilled transitive dependencies
        remove_unfulfilled_dependencies(version_subtree, false, processed)
        valid = true
        version_subtree[:dependencies].each do |k, v|
          valid = false if v[:versions].empty?
        end
        valid
      end
    end
    if dependency[:versions].empty? && raise_on_missing
      raise "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



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/lyp/resolver.rb', line 10

def resolve_package_dependencies
  tree = get_dependency_tree
  
  definite_versions = resolve_tree(tree)
  specifier_map = map_specifiers_to_versions(tree)
  
  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(tree[:available_packages][v][:path])
  end
  
  {
    user_file: @user_file,
    definite_versions: definite_versions,
    package_refs: refs,
    package_dirs: dirs
  }
end

#resolve_tree(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



332
333
334
335
336
337
338
339
340
341
342
343
344
 
# File 'lib/lyp/resolver.rb', line 332

def resolve_tree(tree)
  permutations = permutate_simplified_tree(tree)
  permutations = filter_invalid_permutations(permutations)
  
  user_deps = tree[:dependencies].keys
  result = select_highest_versioned_permutation(permutations, user_deps).flatten
  
  if result.empty? && !tree[:dependencies].empty?
    raise "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



443
444
445
446
 
# File 'lib/lyp/resolver.rb', line 443

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

#set_forced_package_path(tree, package, path) ⇒ Object 



200
201
202
203
204
205
206
207
208
 
# File 'lib/lyp/resolver.rb', line 200

def set_forced_package_path(tree, package, path)
  @opts[:forced_package_paths] ||= {}
  @opts[:forced_package_paths][package] = path
  
  available_packages(tree)["#{package}@forced"] = {
    path: File.join(path, MAIN_PACKAGE_FILE),
    dependencies: {}
  }
end

#simplified_deps_tree(version, 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



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 simplified_deps_tree(version, processed = {})
  return {} unless version[:dependencies]
  
  return processed[version] if processed[version]
  processed[version] = dep_versions = {}

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

  dep_versions
end

#sort_permutations(permutations, user_deps) ⇒ Object

Sort permutations by version numbers



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

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] ||= (Gem::Version.new($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(tree) ⇒ 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.



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

def squash_old_versions(tree)
  specifiers = map_specifiers_to_versions(tree)
  
  compare_versions = lambda do |x, y|
    v_x = x =~ Lyp::PACKAGE_RE && Gem::Version.new($2)
    v_y = y =~ Lyp::PACKAGE_RE && Gem::Version.new($2)
    x <=> y
  end
  
  # Remove old versions for anything but 
  specifiers.each do |package, specifiers|
    # Remove old versions only if the package is referenced from a single
    # specifier
    if specifiers.size == 1
      specifier = specifiers.values.first
      specifier.each do |version_tree|
        # check if all versions have same dependencies. Older versions can be 
        # safely removed only if their dependencies are identical
        deps = version_tree.map {|k, v| v[:dependencies]}
        if deps.uniq.size == 1
          versions = version_tree.keys.sort(&compare_versions)
          latest = versions.last
          version_tree.select! {|v| v == latest}
        end
      end
    end
  end
end