DependencyGraph.js 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418
  1. const { appendDataPath } = require('../../utils/dataPath');
  2. const { Type: ValidationErrorType } = require('../../model/ValidationError');
  3. const { isObject, last } = require('../../utils/objectUtils');
  4. const HasManyRelation = require('../../relations/hasMany/HasManyRelation');
  5. const RelationExpression = require('../RelationExpression');
  6. const ManyToManyRelation = require('../../relations/manyToMany/ManyToManyRelation');
  7. const BelongsToOneRelation = require('../../relations/belongsToOne/BelongsToOneRelation');
  8. const DependencyNode = require('./DependencyNode');
  9. const HasManyDependency = require('./HasManyDependency');
  10. const ManyToManyConnection = require('./ManyToManyConnection');
  11. const ReplaceValueDependency = require('./ReplaceValueDependency');
  12. const BelongsToOneDependency = require('./BelongsToOneDependency');
  13. const InterpolateValueDependency = require('./InterpolateValueDependency');
  14. class DependencyGraph {
  15. constructor(opt, allowedRelations) {
  16. this.allowedRelations = allowedRelations;
  17. this.nodesById = new Map();
  18. this.nodes = [];
  19. this.uid = 0;
  20. this.opt = opt || Object.create(null);
  21. }
  22. build(modelClass, models) {
  23. this.nodesById = new Map();
  24. this.nodes = [];
  25. if (Array.isArray(models)) {
  26. for (let i = 0, l = models.length; i < l; ++i) {
  27. this.buildForModel({
  28. modelClass,
  29. model: models[i],
  30. parentModel: null,
  31. allowedRelations: this.allowedRelations,
  32. dataPath: null,
  33. rel: null
  34. });
  35. }
  36. } else {
  37. this.buildForModel({
  38. modelClass,
  39. model: models,
  40. parentModel: null,
  41. allowedRelations: this.allowedRelations,
  42. dataPath: null,
  43. rel: null
  44. });
  45. }
  46. this.solveReferences();
  47. this.createNonRelationDeps();
  48. if (this.isCyclic(this.nodes)) {
  49. throw modelClass.createValidationError({
  50. type: ValidationErrorType.InvalidGraph,
  51. message: 'the object graph contains cyclic references'
  52. });
  53. }
  54. return this.nodes;
  55. }
  56. buildForModel({ modelClass, model, parentNode, rel, allowedRelations, dataPath }) {
  57. if (!model || !model.$isObjectionModel) {
  58. throw modelClass.createValidationError({
  59. type: ValidationErrorType.InvalidGraph,
  60. message: 'not a model'
  61. });
  62. }
  63. if (!model[modelClass.uidProp]) {
  64. model[modelClass.uidProp] = this.createUid();
  65. }
  66. const node = new DependencyNode({ parentNode, model, modelClass, relation: rel, dataPath });
  67. const isRelate = this.isRelate({ modelClass, model, parentNode, rel });
  68. const dbRef = model[modelClass.dbRefProp];
  69. this.nodesById.set(node.id, node);
  70. this.nodes.push(node);
  71. if (isRelate && dbRef) {
  72. const isComposite = Array.isArray(dbRef);
  73. for (let i = 0; i < rel.relatedProp.size; ++i) {
  74. rel.relatedProp.setProp(model, i, isComposite ? dbRef[i] : dbRef);
  75. }
  76. }
  77. if (rel) {
  78. if (rel instanceof HasManyRelation) {
  79. node.needs.push(new HasManyDependency(parentNode, rel));
  80. parentNode.isNeededBy.push(new HasManyDependency(node, rel));
  81. if (isRelate) {
  82. throw new Error(
  83. `You cannot relate HasManyRelation or HasOneRelation using insertGraph, because those require update operations. Consider using upsertGraph instead.`
  84. );
  85. }
  86. } else if (rel instanceof BelongsToOneRelation) {
  87. node.isNeededBy.push(new BelongsToOneDependency(parentNode, rel));
  88. parentNode.needs.push(new BelongsToOneDependency(node, rel));
  89. if (isRelate) {
  90. // We can resolve the node immediately if we are relating since
  91. // `model` already has the foreign key.
  92. last(node.isNeededBy).resolve(model);
  93. }
  94. } else if (rel instanceof ManyToManyRelation) {
  95. // ManyToManyRelations create no dependencies since we can create the
  96. // join table rows after everything else has been inserted.
  97. parentNode.manyToManyConnections.push(new ManyToManyConnection(node, rel));
  98. }
  99. }
  100. if (isRelate) {
  101. // If the node is a relate node, it already exists in the database.
  102. // Mark it as inserted.
  103. node.markAsInserted();
  104. }
  105. this.buildForRelations({ modelClass, node, allowedRelations, dataPath });
  106. }
  107. buildForRelations({ modelClass, node, allowedRelations, dataPath }) {
  108. const model = node.model;
  109. const relations = modelClass.getRelationArray();
  110. for (let i = 0, l = relations.length; i < l; ++i) {
  111. const rel = relations[i];
  112. const relModels = model[rel.name];
  113. let nextAllowed = null;
  114. if (relModels) {
  115. if (isObject(allowedRelations) && allowedRelations.isObjectionRelationExpression) {
  116. nextAllowed = allowedRelations.childExpression(rel.name);
  117. if (!nextAllowed) {
  118. throw modelClass.createValidationError({
  119. type: ValidationErrorType.UnallowedRelation,
  120. message: 'trying to insert an unallowed relation'
  121. });
  122. }
  123. }
  124. const relPath = appendDataPath(dataPath, rel);
  125. if (Array.isArray(relModels)) {
  126. for (let i = 0, l = relModels.length; i < l; ++i) {
  127. this.buildForModel({
  128. modelClass: rel.relatedModelClass,
  129. model: relModels[i],
  130. parentNode: node,
  131. rel,
  132. allowedRelations: nextAllowed,
  133. dataPath: appendDataPath(relPath, i)
  134. });
  135. }
  136. } else {
  137. this.buildForModel({
  138. model: relModels,
  139. modelClass: rel.relatedModelClass,
  140. parentNode: node,
  141. allowedRelations: nextAllowed,
  142. dataPath: relPath,
  143. rel
  144. });
  145. }
  146. }
  147. }
  148. }
  149. isRelate({ modelClass, model, parentNode, rel }) {
  150. if (!rel) {
  151. return false;
  152. }
  153. if (model[modelClass.dbRefProp]) {
  154. return true;
  155. }
  156. return rel.hasRelateProp(model) && this.hasOption('relate', relationPath(parentNode, rel));
  157. }
  158. hasOption(option, relationPath) {
  159. const opt = this.opt[option];
  160. if (Array.isArray(opt)) {
  161. return opt.indexOf(relationPath) !== -1;
  162. } else {
  163. return !!opt;
  164. }
  165. }
  166. solveReferences() {
  167. const refMap = new Map();
  168. // First merge all reference nodes into the actual node.
  169. this.mergeReferences(refMap);
  170. // Replace all reference nodes with the actual nodes.
  171. this.replaceReferenceNodes(refMap);
  172. }
  173. mergeReferences(refMap) {
  174. for (let n = 0, ln = this.nodes.length; n < ln; ++n) {
  175. const refNode = this.nodes[n];
  176. let ref;
  177. if (refNode.handled) {
  178. continue;
  179. }
  180. ref = refNode.model[refNode.modelClass.uidRefProp];
  181. if (ref) {
  182. const actualNode = this.nodesById.get(ref);
  183. if (!actualNode) {
  184. throw refNode.modelClass.createValidationError({
  185. type: ValidationErrorType.InvalidGraph,
  186. message: `could not resolve reference "${ref}"`
  187. });
  188. }
  189. for (let d = 0, ld = refNode.needs.length; d < ld; ++d) {
  190. actualNode.needs.push(refNode.needs[d]);
  191. }
  192. for (let d = 0, ld = refNode.isNeededBy.length; d < ld; ++d) {
  193. actualNode.isNeededBy.push(refNode.isNeededBy[d]);
  194. }
  195. for (let m = 0, lm = refNode.manyToManyConnections.length; m < lm; ++m) {
  196. actualNode.manyToManyConnections.push(refNode.manyToManyConnections[m]);
  197. }
  198. refMap.set(refNode.id, actualNode);
  199. refNode.handled = true;
  200. }
  201. }
  202. }
  203. replaceReferenceNodes(refMap) {
  204. for (let n = 0, ln = this.nodes.length; n < ln; ++n) {
  205. const node = this.nodes[n];
  206. let d, ld, dep, actualNode;
  207. for (d = 0, ld = node.needs.length; d < ld; ++d) {
  208. dep = node.needs[d];
  209. actualNode = refMap.get(dep.node.id);
  210. if (actualNode) {
  211. dep.node = actualNode;
  212. }
  213. }
  214. for (d = 0, ld = node.isNeededBy.length; d < ld; ++d) {
  215. dep = node.isNeededBy[d];
  216. actualNode = refMap.get(dep.node.id);
  217. if (actualNode) {
  218. dep.node = actualNode;
  219. }
  220. }
  221. for (let m = 0, lm = node.manyToManyConnections.length; m < lm; ++m) {
  222. const conn = node.manyToManyConnections[m];
  223. actualNode = refMap.get(conn.node.id);
  224. if (actualNode) {
  225. conn.refNode = conn.node;
  226. conn.node = actualNode;
  227. }
  228. }
  229. }
  230. }
  231. createNonRelationDeps() {
  232. for (let n = 0, ln = this.nodes.length; n < ln; ++n) {
  233. const node = this.nodes[n];
  234. if (!node.handled) {
  235. this.createNonRelationDepsForObject(node.model, node, []);
  236. }
  237. }
  238. }
  239. createNonRelationDepsForObject(obj, node, path) {
  240. const propRefRegex = node.modelClass.propRefRegex;
  241. const relations = node.modelClass.getRelations();
  242. const isModel = obj && obj.$isObjectionModel;
  243. const keys = Object.keys(obj);
  244. for (let i = 0, l = keys.length; i < l; ++i) {
  245. const key = keys[i];
  246. const value = obj[key];
  247. if (isModel && relations[key]) {
  248. // Don't traverse the relations of model instances.
  249. return;
  250. }
  251. path.push(key);
  252. if (typeof value === 'string') {
  253. allMatches(propRefRegex, value, matchResult => {
  254. const [match, refId, refProp] = matchResult;
  255. const refNode = this.nodesById.get(refId);
  256. if (!refNode) {
  257. throw node.modelClass.createValidationError({
  258. type: ValidationErrorType.InvalidGraph,
  259. message: `could not resolve reference "${value}"`
  260. });
  261. }
  262. if (value === match) {
  263. // If the match is the whole string, replace the value with the resolved value.
  264. // This means that the value will have the same type as the resolved value
  265. // (date, number, etc).
  266. node.needs.push(new ReplaceValueDependency(refNode, path, refProp, false));
  267. refNode.isNeededBy.push(new ReplaceValueDependency(node, path, refProp, true));
  268. } else {
  269. // If the match is inside a string, replace the reference inside the string with
  270. // the resolved value.
  271. node.needs.push(new InterpolateValueDependency(refNode, path, refProp, match, false));
  272. refNode.isNeededBy.push(
  273. new InterpolateValueDependency(node, path, refProp, match, true)
  274. );
  275. }
  276. });
  277. } else if (isObject(value)) {
  278. this.createNonRelationDepsForObject(value, node, path);
  279. }
  280. path.pop();
  281. }
  282. }
  283. isCyclic(nodes) {
  284. let isCyclic = false;
  285. for (let n = 0, ln = nodes.length; n < ln; ++n) {
  286. let node = nodes[n];
  287. if (node.handled) {
  288. continue;
  289. }
  290. if (this.isCyclicNode(node)) {
  291. isCyclic = true;
  292. break;
  293. }
  294. }
  295. this.clearFlags(this.nodes);
  296. return isCyclic;
  297. }
  298. isCyclicNode(node) {
  299. if (!node.visited) {
  300. node.visited = true;
  301. node.recursion = true;
  302. for (let d = 0, ld = node.needs.length; d < ld; ++d) {
  303. let dep = node.needs[d];
  304. if (!dep.node.visited && this.isCyclicNode(dep.node)) {
  305. return true;
  306. } else if (dep.node.recursion) {
  307. return true;
  308. }
  309. }
  310. }
  311. node.recursion = false;
  312. return false;
  313. }
  314. clearFlags(nodes) {
  315. for (let n = 0, ln = nodes.length; n < ln; ++n) {
  316. let node = nodes[n];
  317. node.visited = false;
  318. node.recursion = false;
  319. }
  320. }
  321. createUid() {
  322. return `__objection_uid(${++this.uid})__`;
  323. }
  324. }
  325. function allMatches(regex, str, cb) {
  326. let matchResult = regex.exec(str);
  327. while (matchResult) {
  328. cb(matchResult);
  329. matchResult = regex.exec(str);
  330. }
  331. }
  332. function relationPath(parentNode, rel) {
  333. let path = '';
  334. while (parentNode !== null && parentNode.relation !== null) {
  335. path = parentNode.relation.name + (path ? '.' : '') + path;
  336. parentNode = parentNode.parentNode;
  337. }
  338. return path + (path ? '.' : '') + (rel ? rel.name : '');
  339. }
  340. module.exports = DependencyGraph;