/* @flow */
/**
 *  Copyright (c) 2015, Facebook, Inc.
 *  All rights reserved.
 *
 *  This source code is licensed under the BSD-style license found in the
 *  LICENSE file in the root directory of this source tree. An additional grant
 *  of patent rights can be found in the PATENTS file in the same directory.
 */

import { visit } from '../language/visitor';
import type {
  DocumentNode,
  FragmentDefinitionNode,
  OperationDefinitionNode,
} from '../language/ast';

/**
 * separateOperations accepts a single AST document which may contain many
 * operations and fragments and returns a collection of AST documents each of
 * which contains a single operation as well the fragment definitions it
 * refers to.
 */
export function separateOperations(
  documentAST: DocumentNode
): { [operationName: string]: DocumentNode } {

  const definitions: DefinitionMap = Object.create(null);
  const depGraph: DepGraph = Object.create(null);
  let fromName;
  let idx = 0;

  // Populate the list of definitions and build a dependency graph.
  visit(documentAST, {
    OperationDefinition(node) {
      fromName = opName(node);
      definitions[fromName] = { idx, node };
      ++idx;
    },
    FragmentDefinition(node) {
      fromName = node.name.value;
      definitions[fromName] = { idx, node };
      ++idx;
    },
    FragmentSpread(node) {
      const toName = node.name.value;
      (depGraph[fromName] ||
        (depGraph[fromName] = Object.create(null)))[toName] = true;
    }
  });

  // For each operation, produce a new synthesized AST which includes only what
  // is necessary for completing that operation.
  const separatedDocumentASTs = Object.create(null);
  const operationNames = Object.keys(definitions).filter(defName =>
    definitions[defName].node.kind === 'OperationDefinition'
  );
  operationNames.forEach(operationName => {
    const dependencies = Object.create(null);
    collectTransitiveDependencies(dependencies, depGraph, operationName);
    dependencies[operationName] = true;

    separatedDocumentASTs[operationName] = {
      kind: 'Document',
      definitions: Object.keys(dependencies)
        .map(defName => definitions[defName])
        .sort((def1, def2) => def1.idx - def2.idx)
        .map(def => def.node)
    };
  });

  return separatedDocumentASTs;
}

type DefinitionMap = {
  [defName: string]: {
    idx: number,
    node: OperationDefinitionNode | FragmentDefinitionNode
  }
};
type DepGraph = {[from: string]: {[to: string]: boolean}};

// Provides the empty string for anonymous operations.
function opName(operation: OperationDefinitionNode): string {
  return operation.name ? operation.name.value : '';
}

// From a dependency graph, collects a list of transitive dependencies by
// recursing through a dependency graph.
function collectTransitiveDependencies(
  collected: {[key: string]: boolean},
  depGraph: DepGraph,
  fromName: string
): void {
  const immediateDeps = depGraph[fromName];
  if (immediateDeps) {
    Object.keys(immediateDeps).forEach(toName => {
      if (!collected[toName]) {
        collected[toName] = true;
        collectTransitiveDependencies(collected, depGraph, toName);
      }
    });
  }
}

@@ -391,34 +391,8 @@
 de,%0A
-  FragmentDefinitionNode,%0A
   Op
@@ -813,55 +813,94 @@
 nst 
-definitions: DefinitionMap = Object.create(null
+operations = %5B%5D;%0A  const fragments = Object.create(null);%0A  const positions = new Map(
 );%0A 
@@ -998,31 +998,16 @@
 ate 
-the list of definitions
+metadata
  and
@@ -1129,53 +1129,37 @@
     
-definitions%5BfromName%5D = %7B idx, 
+operations.push(
 node
- %7D
+)
 ;%0A      
 ++id
@@ -1146,37 +1146,58 @@
 sh(node);%0A      
-++idx
+positions.set(node, idx++)
 ;%0A    %7D,%0A    Fra
@@ -1260,26 +1260,24 @@
 ;%0A      
-definition
+fragment
 s%5BfromNa
@@ -1285,30 +1285,21 @@
 e%5D =
- %7B idx,
  node
- %7D
 ;%0A      
 ++id
@@ -1298,13 +1298,34 @@
     
-++idx
+positions.set(node, idx++)
 ;%0A  
@@ -1688,22 +1688,16 @@
 ull);%0A  
-const 
 operatio
@@ -1701,149 +1701,65 @@
 tion
-Names = Object.keys(definitions).filter(defName
+s.forEach(operation
  =%3E
+ %7B
 %0A    
-definitions%5BdefName%5D.node.kind === 'OperationDefinition'%0A  );%0A  operationNames.forEach
+const operationName = opName
 (ope
@@ -1764,25 +1764,18 @@
 peration
-Name =%3E %7B
+);
 %0A    con
@@ -1891,123 +1891,154 @@
 e);%0A
+%0A
     
-dependencies%5BoperationName%5D = true;%0A%0A    separatedDocumentASTs%5BoperationName%5D = %7B%0A      kind: 'D
+// The list of definition nodes to be included for this operation, sorted%0A    // to retain the same order as the original d
 ocument
-',
+.
 %0A    
- 
+const
  def
@@ -2045,17 +2045,37 @@
 initions
-:
+ = %5B operation %5D;%0A   
  Object.
@@ -2096,313 +2096,310 @@
 ies)
-%0A        .map(defName =%3E definitions%5BdefName%5D)%0A        .sort((def1, def2) =%3E def1.idx - def2.idx)%0A        .map(def =%3E def.node)%0A    %7D;%0A  %7D);%0A%0A  return separatedDocumentASTs;%0A%7D%0A%0Atype DefinitionMap = %7B%0A  %5BdefName: string%5D:
+.forEach(name =%3E %7B%0A      definitions.push(fragments%5Bname%5D)%0A    %7D);%0A    definitions.sort(%0A      (n1, n2) =%3E (positions.get(n1) %7C%7C 0) - (positions.get(n2) %7C%7C 0)%0A    );%0A%0A    separatedDocumentASTs%5BoperationName%5D =
  %7B%0A    
+  
-idx: number,%0A    node: OperationDefinitionNode %7C FragmentDefinitionNode%0A  %7D%0A%7D;
+kind: 'Document',%0A      definitions%0A    %7D;%0A  %7D);%0A%0A  return separatedDocumentASTs;%0A%7D%0A
 %0Atyp

Use a Map<Node> for original indices