Module: CSVPlusPlus::Runtime::Graph

Defined in:
lib/csv_plus_plus/runtime/graph.rb

Overview

Graph ordering and searching functions

Defined Under Namespace

Classes: DependencyGraph

Class Method Summary collapse

Class Method Details

.dependency_graph(variables) ⇒ Object

Create a dependency graph of variables



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

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

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

Do a DFS on an AST starting at node



46
47
48
49
50
51
52
53
54
 
# File 'lib/csv_plus_plus/runtime/graph.rb', line 46

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

  return accum unless node.is_a?(::CSVPlusPlus::Entities::FunctionCall)

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

.topological_sort(dependencies) ⇒ Object

TODO: I don’t think we use this anymore - it was useful when I wanted to resolve variables in their dependency

order

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]



41
42
43
 
# File 'lib/csv_plus_plus/runtime/graph.rb', line 41

def self.topological_sort(dependencies)
  dependencies.tsort
end

.variable_references(ast, 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



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

def self.variable_references(ast, include_runtime_variables: false)
  depth_first_search(ast) do |node|
    next unless node.is_a?(::CSVPlusPlus::Entities::Reference)

    node.id if !::CSVPlusPlus::Entities::Builtins.builtin_variable?(node.id) || include_runtime_variables
  end
end