Module: CSVPlusPlus::Graph

Defined in:
lib/csv_plus_plus/graph.rb

Overview

Graph ordering and searching functions

Defined Under Namespace

Classes: DependencyGraph

Class Method Summary collapse

Class Method Details

.dependency_graph(variables, runtime) ⇒ Object

Create a dependency graph of variables



20
21
22
23
24
 
# File 'lib/csv_plus_plus/graph.rb', line 20

def self.dependency_graph(variables, runtime)
  ::CSVPlusPlus::Graph::DependencyGraph[
    variables.map { |var_id, ast| [var_id, variable_references(ast, runtime)] }
  ]
end

.depth_first_search(node, accum = []) ⇒ Object

Do a DFS on an AST starting at node



42
43
44
45
46
47
48
49
50
 
# File 'lib/csv_plus_plus/graph.rb', line 42

def self.depth_first_search(node, accum = [], &)
  ret = yield(node)
  accum << ret unless ret.nil?

  return accum unless node.function_call?

  node.arguments.each { |n| depth_first_search(n, accum, &) }
  accum
end

.topological_sort(dependencies) ⇒ Object

Perform a topological sort on a DependencyGraph. A toplogical sort is noteworthy because it will give us the order in which we need to resolve our variable dependencies.

Given this dependency graph:

{ a: [b c], b: [c], c: [d], d: [] }

it will return:

[d, c, b, a]



37
38
39
 
# File 'lib/csv_plus_plus/graph.rb', line 37

def self.topological_sort(dependencies)
  dependencies.tsort
end

.variable_references(ast, runtime, include_runtime_variables: false) ⇒ Object

Get a list of all variables references in a given ast TODO: this is only used in one place - refactor it



11
12
13
14
15
16
17
 
# File 'lib/csv_plus_plus/graph.rb', line 11

def self.variable_references(ast, runtime, include_runtime_variables: false)
  depth_first_search(ast) do |node|
    next unless node.variable?

    node.id if !runtime.runtime_variable?(node.id) || include_runtime_variables
  end
end