cyclic dependencies

[ghost]

Hey everyone.

@kumavis and I have been hard at work trying to find an efficient way to move THREE.js over to a browserify architecture. We made good progress, even up to the point of having all of the files moved over to a browserify build system and being able to generate a three.min.js with gulp.

Unfortunately, the examples don't work, because unlike commonjs browserify cannot handle cyclic dependencies, of which there are many in THREE.js.

I have made an interactive graph depicting the dependency relationships here.

Unless and until these get untangled, we will not be able to move THREE.js over to a browserify build.

I do not consider this a deficiency of browserify, but rather a problem with THREE.js. Circular dependencies are a bad thing to have in software in general, and lead to all sorts of problems.

[kumavis]

thats quite a knot to untangle
http://jsbin.com/medezu/2/edit?html,js,output

[kumavis]

@coballast can you post the code you used to generate the dependency json?

[bhouston]

Just use the precompiled three.min.js file directly. There is no need to break up Three.js into individual files within Browserfy, you are just making your life more difficult for no real benefit.

[bhouston]

I speak from experience, in that we use the npm module of three.js and it works great. We just package it up as a single file and wrap it in a CommonJS style module. This approach would work for browserfy and a lot of people are already doing it I understand.

Untangling this knot isn't needed for this use case.

[ghost]

@kumavis I just dumped the dependency structure. The following code then generated the graph:

var fs = require('fs-extra');
var unique = require('uniq');
var util = require('util');

function getRequiredObjects(dependencies){
  var result = [];
  for(var i = 0; i < dependencies.usedObjects.length; i++){
    var object = dependencies.usedObjects[i];
    if(dependencies.definedObjects.indexOf(object) == -1)
      result.push(object);
  }

  return result;
};

var dependencies = JSON.parse(fs.readFileSync('./dependencies.json'));

var objects = [];
for(var f in dependencies){
  objects = objects.concat(dependencies[f].usedObjects);
  objects = objects.concat(dependencies[f].definedObjects);
}

objects = unique(objects);


var nodes = objects.map(function(o){
  return {data: {id: o} };
});

var edges = [];
for(var f in dependencies){
  var dependency = dependencies[f];
  var requiredObjects = getRequiredObjects(dependency);
  for(var j = 0; j < dependency.definedObjects.length; j++){
    for(var k = 0; k < requiredObjects.length; k++){
      edges.push({ data: { source: dependency.definedObjects[j], target: requiredObjects[k] } });
    }
  }
}

var graph = {nodes: nodes, edges: edges};

var eliminateImpossibleCycleNodes = function(graph){
  graph.nodes = graph.nodes.filter(function(node){
    var source_edge = null;
    var dest_edge = null;
    for(var i = 0; i < graph.edges.length; i++){
      if(graph.edges[i].data.source == node.data.id)
        source_edge = graph.edges[i];
      if(graph.edges[i].data.target == node.data.id)
        dest_edge = graph.edges[i];
    }

    if(source_edge != null && dest_edge != null)
      return true;
    else
      return false;
  });

  graph.edges = graph.edges.filter(function(edge){
    var source_exists = false, target_exists = false;
    for(var i = 0; i < graph.nodes.length; i++){
      if(edge.data.source == graph.nodes[i].data.id)
        source_exists = true;
      if(edge.data.target == graph.nodes[i].data.id)
        target_exists = true;
    }

    return source_exists && target_exists;
  });
};

for(var i = 0; i < 500; i++)
  eliminateImpossibleCycleNodes(graph)


console.log(JSON.stringify(graph));

[kumavis]

@bhouston its more about the health of the three.js codebase

[bhouston]

I just know that in the math library, which I helped with a fair bit, cyclic dependences are the norm in all languages. Because functions on Matrix4 may take Vector3 as parameters, and Vector3 may be able to be transformed by Matrix4. To make all dependencies one way in the math library would make that part of the library annoying to use.

Now I do advocate that the math library does not know about any other part of the library -- more complex types should not really leak into that module. Thus in that sense I advocate trying to reduce inter-module cyclic dependences, but not removing all cyclic dependences between individual files within a module.

[kumavis]

Here is a case that illustrates the subtle complications. To be clear, here I am not critical of the implementation itself, but the side effects.

Vector3 and Matrix4 form a cyclical dependency because they expose a range of functions that use each other as input or output types. Both are implemented with a style common to Three.js, defining functions via IIFEs to include scratch variables for performing calculations.

Matrix4#lookAt is able to instantiate the scratch immediately, as part of the function definition.

lookAt: function () {

  var x = new THREE.Vector3();
  var y = new THREE.Vector3();
  var z = new THREE.Vector3();

  return function ( eye, target, up ) {
    /* ... */

Vector3#project however, must instantiate the scratch on first run.

project: function () {

  var matrix;

  return function ( camera ) {

    if ( matrix === undefined ) matrix = new THREE.Matrix4();

    /* ... */

Why? because when defining the Class, not all Classes have yet been defined. When defining Vector3, Matrix4 does not exist yet. Now the actual instantiation time of the scratch variables is not really important. The real takeaway here is that the current implementation hinges on the order that the build system concatenates files together. That is a really distant coupling, and changes to the build system or renaming of files in such a way that it changes concat order can result in invalid builds, with no obvious connection.

This is just one of the ways that this knot manifests into bugs. However, while we can address this specific issue, I don't have a general solution that doesn't require a lot of breaking changes to the API.

[bhouston]

Hmm... I had a look at ILM's C++ math library, which I consider to be the gold standard in terms of math libraries. Surprisingly, they are not cyclic. They basically have a well defined order of simple to complex types that they define and I guess if you do it very carefully it works:

https://github.com/openexr/openexr/tree/master/IlmBase/Imath

Math and then Vec seems to be the simpliest.

[kumavis]

Further observations on the dependency graph:

Materials have two-way deps with their base class

A little hard to see, but Geometrys seem to have good one-way deps on the base class

Lights and Cameras have a similar situation -- good in respect to their base class, but Object3D's dependency on them seems unnecessary.


Curves Paths Lines seem good, but Shape is a bit tangled.

[kumavis]

@coballast thanks! this is great insight.

[makc]

Adding myself for the comments :)

Btw, I have looked in the way Material depends on MeshDepthMaterial, for example. It is simple

if ( this instanceof THREE.MeshDepthMaterial )

which is trivial to change to

if ( this.type == 'MeshDepthMaterial' )

and voila - no dependency. I guess half of this scary graph is the same level of problem.

[makc]

funny thing is that this dependency takes place in single toJSON method. I mean, couldn't it be just replaced in MeshDepthMaterial instead? something like

THREE.MeshDepthMaterial.prototype.toJSON =  function () {
    var output = THREE.Material.prototype.toJSON.apply(this);
    if ( this.blending !== THREE.NormalBlending ) output.blending = this.blending;
    if ( this.side !== THREE.FrontSide ) output.side = this.side;

[kumavis]

@makc In general anywhere we are doing instanceof we should move that code on to the specific class itself. That will help remove a lot of the knots.

[zz85]

just wanted to say while AMD doesn't support circular references, ES6 modules does https://github.com/ModuleLoader/es6-module-loader/wiki/Circular-References-&-Bindings

i'm just curious to know apart from the dependency resolving problem (which can be solved in the implementation of a module system loader eg. system.js), what issues does circular referencing in three.js create?

[ghost]

Fortunately it looks like we can attack this in stages. I think a lot of api breaking changes have been made in previous releases, so I am not sure that is out of the question.

[kumavis]

For the instanceof cases (perhaps the majority) they should be able to be resolved w/o breaking changes.

[gero3]

I'm also subscribing here. Let's go step by step here.
I agree we should remove all unnecessary cyclic dependencies like the material one.
I also agree with @bhouston that the math library is just very dependent on each other because the interaction is what makes the math library useful.

Can someone map out the easy ones?? Having less cyclic dependencies is always a good idea if it doesn't hamper the library. We can later on see what to do with the others.

@zz85 I have also run into the problem of circular dependencies. It is mostly a problem for when we are trying to pre-create certain objects inside circular referenced files.

[kumavis]

#6252 should clear up a lot of circular deps on Material and Object3D.

[kumavis]

Here's what Mesh looks like. Maybe some extraneous deps but not too crazy.

Circular with Object3D and Geometry. The Object3D -> Mesh reference is addressed in the PR above. The Mesh -> Geometry reference is fine, b/c Mesh controls an instance of Geometry. It could still be broken off b/c its doing type-checking for Class-specific behaviour (Geometry/BufferGeometry).

As for the Geometry -> Mesh reference, it is to provide geometry.mergeMesh( mesh ). Geometry is a lower-level concept than Mesh, so I would invert it as mesh.mergeIntoGeometry( geo ) and deprecate mergeMesh.

[ghost]

If someone gets a pr merged that fixes some of these, let me know and I will update the graph to reflect the current state of affairs.

[ghost]

@bhouston @gero3 I am not convinced that cyclic dependencies are required to get the same level of usability/utility for the math library. I could be wrong, but couldn't we keep Vector3 completely isolated/ignorant of the rest of the system and modify its prototype to accomodate Matrix4's in the Matrix4 module? That makes sense to me conceptually, since Matrices are more complex than Vectors. I think it is better to have a well defined order in which prototypes and classes are constructed to prevent mishaps.

[ghost]

@bhouston @gero3 I think we may be able to do that without changing the api at all. I'll poke around and see what's what.

[makc]

regarding math thing, you could just have all the "scratch pads" sit in single place, I guess. but I bet there will be no single useable graph of 3js that would not have both Vector3 and Matrix4

[bhouston]

If there is a solution that doesn't change the performance or API of the math library, I am all for it.

[kumavis]

@coballast cant remove the cyclical dep w/o an API change, b/c both provide methods that use the other type. Vector3 Matrix4

As for browserify compat, our only requirement is to move the instantiation on the scratch vars out of class-definition time (make them instantiate on the first run). Make this lazy like this. That would have no impact on API or perf.

[bhouston]

I think those types of changes are okay.

[ghost]

@kumavis Ah! Yes. Okay, I understand now. That's easy enough.

[mrdoob]

Now that Raycaster is more lightweight we could give it go at making it like the rest of the classes.

[roomle-build]

@mrdoob, @Mugen87 we use Rollup to only use the parts of Three.js we really need. When we run the built we still get the following warning:

(!) Circular dependency: node_modules/three/src/math/Vector3.js -> node_modules/three/src/math/Matrix4.js -> node_modules/three/src/math/Vector3.js
(!) Circular dependency: node_modules/three/src/math/Vector3.js -> node_modules/three/src/math/Quaternion.js -> node_modules/three/src/math/Vector3.js
(!) Circular dependency: node_modules/three/src/math/Sphere.js -> node_modules/three/src/math/Box3.js -> node_modules/three/src/math/Sphere.js
(!) Circular dependency: node_modules/three/src/objects/LineSegments.js -> node_modules/three/src/objects/Line.js -> node_modules/three/src/objects/LineSegments.js

Are there still circular dependencies in Three.js or are we doing something wrong?

[bhouston]

Vector3 and Matrix4 are tied to each other, if you pull in one, you need to pull in the other. Circular dependencies should technically be allowed.

[roomle-build]

@bhouston yeah I see, thanks for the hint. Yes circular dependencies are allowed and rollup makes no troubles but I'm not sure if it's good practice to have circular dependencies. Vector3 only depends on Matrix4 because of multiplyMatrices and getInverse, for more details see (https://github.com/mrdoob/three.js/blob/dev/src/math/Vector3.js#L315)

[makc]

@roomle-build Idk, man, just because it explicitly references the Matrix4 constructor? what about

	applyMatrix4: function ( m ) {

		var x = this.x, y = this.y, z = this.z;
		var e = m.elements;

		var w = 1 / ( e[ 3 ] * x + e[ 7 ] * y + e[ 11 ] * z + e[ 15 ] );

		this.x = ( e[ 0 ] * x + e[ 4 ] * y + e[ 8 ] * z + e[ 12 ] ) * w;
		this.y = ( e[ 1 ] * x + e[ 5 ] * y + e[ 9 ] * z + e[ 13 ] ) * w;
		this.z = ( e[ 2 ] * x + e[ 6 ] * y + e[ 10 ] * z + e[ 14 ] ) * w;

		return this;

},

?

you can say that you could pass { elements: [....] } and it will work, but we all know it expects Matrix4 there

[mrdoob]

Lets start with Vector3.

Vector3 depends on Matrix4 because of project and unproject:

	project: function () {

		var matrix = new Matrix4();

		return function project( camera ) {

			matrix.multiplyMatrices( camera.projectionMatrix, matrix.getInverse( camera.matrixWorld ) );
			return this.applyMatrix4( matrix );

		};

	}(),

	unproject: function () {

		var matrix = new Matrix4();

		return function unproject( camera ) {

			matrix.multiplyMatrices( camera.matrixWorld, matrix.getInverse( camera.projectionMatrix ) );
			return this.applyMatrix4( matrix );

		};

	}(),

Vector3 depends on Quaternion because of applyEuler and applyAxisAngle:

	applyEuler: function () {

		var quaternion = new Quaternion();

		return function applyEuler( euler ) {

			if ( ! ( euler && euler.isEuler ) ) {

				console.error( 'THREE.Vector3: .applyEuler() now expects an Euler rotation rather than a Vector3 and order.' );

			}

			return this.applyQuaternion( quaternion.setFromEuler( euler ) );

		};

	}(),

	applyAxisAngle: function () {

		var quaternion = new Quaternion();

		return function applyAxisAngle( axis, angle ) {

			return this.applyQuaternion( quaternion.setFromAxisAngle( axis, angle ) );

		};

	}(),

Suggestions?

[roomle-build]

I'm not sure if we need to remove circular dependencies by all means. But I could imagine to move multiplyMatrices to a Math module. The signature would then change of course to multiplyMatrices( a: Matrix4, b: Matrix4, result: Matrix4 ): Matrix4. Inside Vector3 you could then import { multiplyMatrices } from './Math'; the same could be done in Matrix4 (to keep the API surface of Matrix4 the same).

I just had a quick look (didn't look at the Quaternian case - only Vec3/Mat4) and I'm also not sure about performance implication and consequences for the rest of the code base. Furthermore I'm also not convinced that it's absolutely necessary to remove these circular dependencies. Just wanted to share my thought because @mrdoob asked for suggestions

[makc]

@roomle-build so basically create more modules for the sake of no circular dependencies, but you're still going to use all those modules? this maybe could make more sense if each and every math method would be its own module, then you're pulling in only those you use, but that will be a lot of modules.

[roomle-build]

@makc not really. It would be one big module with a lot of small "helper" functions. This would also help for tree-shaking etc. A math module could look like:

export const multiplyMatrices( a, b, result ) { // ... DO STUFF ... // }
export const getInverse( /* ... */ ) { // ... DO STUFF ... // }
// ...
// ...

And the consuming module would do something like:

import { Matrix4 } from './Matrix4.js';
import { multiplyMatrices } from './math';
const result = new Matrix4( );
multiplyMatrices( a, b, result );

When bundleing everything together, rollup does it's magic and creates the most efficient bundle.

This is what a lot of popular libraries are doing. Actually RxJS switched their import "logic" also to the pattern I described. There it looks something like:

 import { flatMap, map, tap } from 'rxjs/operators';

myObject.run().pipe(
  tap(result => doSomething()), 
  flatMap(() => doSomethingElse()), 
  map(() => doAnotherThing())
);

You can read about the "why and how" they changed this stuff in RxJS 6 in several blogposts for example: https://auth0.com/blog/whats-new-in-rxjs-6/

But as I said, it's just a thought and I'm not sure about all the implications this would have to the rest of the codebase. Also the current math module is not "prepared" to be used like this. Currently all the methods on the math module are attached "kind of static". This also prevents rollup from detecting what's really needed...

[makc]

@roomle-build hmm so you're saying that rollup can understand if the code in the same scope does not actually need the whole scope, nice.

[bhouston]

You are talking about moving towards a functional approach (functions taking objects) rather than object oriented approach (object having member functions.) This is a real thing but given that Three.JS is fully object-oriented, proposing this type of change is a pretty big one and it would break all existing code.

I am not sure that the arguments in favor of this change are that significant at this point to justify breaking all backwards compatibility.

[bhouston]

@makc not really. It would be one big module with a lot of small "helper" functions. This would also help for tree-shaking etc. A math module could look like:

If this is what is being proposed, it should be described correctly. It is the change of Three.JS from a object-oriented style of design to a functional design.

[roomle-build]

@roomle-build hmm so you're saying that rollup can understand if the code in the same scope does not actually need the whole scope, nice.

yes rollup understands how all the imports relate to each other and does tree-shaking, dead code elimination etc. The new versions of rollup can also do "chunking" and a lot of other nice stuff. But the current project structure does not take full advantage of these features.

You are talking about moving towards a functional approach (functions taking objects) rather than object oriented approach (object having member functions.) This is a real thing but given that Three.JS is fully object-oriented, proposing this type of change is a pretty big one and it would break all existing code.

I don't think these two paradigms are mutually exclusive. I think you can mix and match these two paradigms. I also don't propose to change to functional programming. I just wanted to describe a way to get rid of the cyclic dependency. You could also attach the multiplyMatrices method to the Math object. But if someone rewrites this kind of stuff it would make sense to consider using the features of ES6 modules. But as I said, I'm not an expert of the Three.js codebase and it was just a thought how to eliminate the cyclic dependency. I think Three.js is an awesome project with a great code base and I don't want to nag around. So I hope no one feels offended by my comments 😉

I'm not sure if we should discuss design decissions in an issue. Do you have some place where this kind of stuff fits better?

[bhouston]

BTW gl-matrix is a functional math library: https://github.com/toji/gl-matrix/tree/master/src/gl-matrix

[mrdoob]

@roomle-build

Currently all the methods on the math module are attached "kind of static".

How so?

[bhouston]

@mrdoob I believe that with the functional design of gl-matrix each function of say vec3 (in the vec3 file I linked to in my previous comment) is exported individually. This allows you to pick and choose which functions to import. You do not need to bring along all of vec3.

Where as with Three.JS, because it uses an object-oriented design, all of the math functions for Vector3 are attached to the Vector3 object prototype and you import just the Vector3 class itself.

Thus the imports in Three.JS are of whole classes whereas with a functional approach you import individual functions.

(The other very neat thing about gl-matrix library is that all the individual functions do not use other functions, @toji has basically inlined an optimized version of all of the mathematics into each individual operation. This is likely quite efficient in terms of speed but it leads to a difficult to maintain library.)

[bhouston]

I do not think we need to refactor this part of Three.JS except maybe to get rid of any references in /math to other directories in three.js. The math library is fairly small and it never really shows up in my profiling tests these days. Yes, it isn't maximally efficient, but it is close enough while maintainable readability and ease of use.

[mrdoob]

@bhouston Got it. Many thanks for the explanation! 😊

[roomle-build]

I just wanted to follow up on the topic. But I want to come back from importing function vs importing classes to the topic of resolving cyclic dependencies. (Also I don't see why import { someFunction } from 'SomeModule' is less maintainable than import SomeClass from 'SomeModule', but that's definitely not the topic of this issue/conversation.

To resolve the cyclic dependency it would be possible to put the functionality into a separate Class. You could attach a multiplyMatrices method to the Math-Class or create a Multiplier-Class which has the multiplyMatrices method. But as I said before I'm not sure if we have to remove cyclic dependencies. If the decision is to not remove them, I think this issue could be close 😃

[Mugen87]

After resolving #19137, this can be closed now 🎉.

[kumavis]

@Mugen87 wow, 5 years! congrats on finally hitting it 🔥 👏
I had a lot of fun making those graphs back then 😸