Function BuildQueryGraph

src/graph/query_graph.c:371–440

build a query graph from AST

// build a query graph from AST
QueryGraph *BuildQueryGraph
(
	const AST *ast
) {
	uint node_count;
	uint edge_count;

	// AST clauses containing path objects
	cypher_astnode_type_t clause_types [2] = {CYPHER_AST_MATCH, CYPHER_AST_MERGE};

	// the initial node and edge arrays will be large enough to accommodate
	// all AST entities (which is overkill, consider reducing)
	node_count = edge_count = raxSize(ast->referenced_entities);
	QueryGraph *qg = QueryGraph_New(node_count, edge_count);

	// for each relevant clause type
	for(int i = 0; i < 2; i ++) {
		const uint8_t clause_type = clause_types[i];
		// collect all path objects
		const cypher_astnode_t **clauses = AST_GetTypedNodes(ast->root,
															 clause_type);
		uint clause_count = array_len(clauses);

		// for each clause of the current type
		for(uint j = 0; j < clause_count; j ++) {
			const cypher_astnode_t *clause = clauses[j];
			// collect path objects
			const cypher_astnode_t **paths =
				AST_GetTypedNodes(clause, CYPHER_AST_PATTERN_PATH);
			const cypher_astnode_t **shortest_paths =
				AST_GetTypedNodes(clause, CYPHER_AST_SHORTEST_PATH);

			// differentiate between regular paths and shortest paths
			// as a path can be marked as shortest
			uint  path_count           =  array_len(paths);
			uint  shortest_path_count  =  array_len(shortest_paths);
			bool only_shortest[path_count];
			memset(only_shortest, 0, path_count*sizeof(bool));

			uint l = 0;  // index to paths array
			uint k = 0;  // index to shortest paths array
			for (; k < shortest_path_count; k++) {
				const cypher_astnode_t *shortest = shortest_paths[k];
				// single shortest paths are handled by a procedure
				if(cypher_ast_shortest_path_is_single(shortest)) continue;

				const cypher_astnode_t *path =
					cypher_ast_shortest_path_get_path(shortest);

				// seek the matching path in the paths array
				while(paths[l] != path) l++;
				ASSERT(l < path_count);

				// each shortest must find its counterpart path
				only_shortest[l] = true;
				l++; // advance for next match
			}
			array_free(shortest_paths);