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.

[AndrewRayCode]

I fully support THREE being broken up into smaller modules with a require structure, for the following reasons:

1. THREE is very large. If a user could require only what they need it might cut down on client build sizes. For example react-bootstrap lets you do things like var Alert = require('react-bootstrap/lib/Alert'); which doesn't bundle every bootstrap module.
2. There are some "plugins", like OrbitControls.js which modify the THREE global object itself, putting itself on THREE.OrbitControls. This is an anti-pattern in modern javascript frameworks because it requires THREE to be present on the global namespace in a build process, instead of required by the files that need it. THREE also does this internally, always modifying the THREE namespace, which is not ideal for including specific THREE modules.

[makc]

putting itself on THREE.OrbitControls

but each and every piece of code in 3js does that?

[bhouston]

@DelvarWorld wrote:

I fully support THREE being broken up into smaller modules with a require structure, for the following reasons:

I used to think it was a good idea to break it up, but there is a simplicity to ThreeJS as it is right now. It is more usable by those new to 3D in the form that it is right now and that has been a priority for the dev team. You can use ThreeJS without needing a module system (of which there are a lot, and they are not all fully compatible.)

[antont]

Like @makc, I'm also puzzled about @DelvarWorld 's suggestion of not putting things in the THREE namespace.

Where / how would they be instead?

To me it seems like the good pattern to create only one global object, THREE, in which all the parts (and possibly some extensions / plugins) of it are.

[kumavis]

I agree with @DelvarWorld that the put-it-on-the-global technique is not good for the health of the codebase -- its a sort of subtle argument b/c putting it on the global itself is not the problem, its the hidden dependency graph, and other practices that come out of having the global available.

But that argument is mostly limited to the internal development and code structure. As for delivering the library as a static code bundle, putting all classes on the global THREE makes sense to me.

A counter argument is that when deserializing a THREE.js scene json, the entries can just list their class as a string which can be pulled off of the global like: THREE[ obj.type ]. This works with classes not in the standard three.js lib as long as you define them on THREE before you deserialize. Not sure how best to replace this behaviour without the THREE global.

[bhouston]

This works with classes not in the standard three.js lib as long as you define them on THREE before you deserialize. Not sure how best to replace this behaviour without the THREE global.

You can do this pattern (or some variant of it) if everything is a module:

var objectType = require( "THREE." + obj.type );

There are a lot of changes coming with ES6 with regards to modules. I'd revisit the modularity of ThreeJS at that point.

[AndrewRayCode]

The built version of three (the javascript file that people can manually download) would still have everything on the three namespace. you could do this with the entry point file for the build being:

var THREE = {
    Geometry: require("./geometry"),

etc, which would still be useful to newcomers, and easy to get started with.

For those using three from npm and requirejs/browserify/webpack in a modern javascript build, we could do something like

var Scene = require("three/scene"),
     Camera = require("three/camera"),

etc, which might cut down on some of the size of three built into a client size bundle. I could be wrong because I don't know how much of three is "core". Right now, though, this is impossible because three doesn't use require statements.

either way the modern pattern is require modules, and instead of making all of your code modify another library (modifying the global THREE, bad), your code is independent and modular, and specifies what it requires with require statements, such as the React source code.

I don't think that me trying to make a full argument for using require/module syntax will be helpful, since there are many good resources online about it. But it is bad to encourage others to modify the THREE namespace for adding plugins like OrbitControls.

[bhouston]

Just be aware @DelvarWorld that ES6 introduces modules officially into JavaScript with a very specific and distinct syntax:

http://www.2ality.com/2014/09/es6-modules-final.html

[AndrewRayCode]

@bhouston oh yeah totally, I'm agnostic to require vs import (import is probably the better choice), just supporting the module pattern in general.

[ghost]

@bhouston @DelvarWorld @kumavis One of my long term projects is to write an automatic es5 -> es6 converter that can accommodate and convert commonjs/amd modules to es6, and hopefully identify and rewrite a lot of javascript using es6 constructs like classes/generators and so on. One could use a browserify transform like es6ify while browsers are catching up to the standard to prepare the code for consumption. Getting THREE moved over to browserify just at the internal level is a good first step to prepare it for input to such a tool.

This is beside the point I was (apparently very poorly) trying to make though. I want to remove as much of these cyclic dependencies as possible, independent of any modularity concerns, because I believe it will make THREE more stable, flexible, and will probably eliminate a lot of bugs as a pleasant side effect.

[kumavis]

@coballast https://github.com/mrdoob/three.js/pull/6252 was merged, should cut down on a lot of the cyclical deps. Think you can generate a new dep graph? Maybe make it a utility in the conversion tool repo

[kumavis]

next is: making the scratch vars in Vector3 Matrix4 defined lazily on first use, not on definition time

anyone want to volunteer? should be quick

[ghost]

Graph has been updated. http://jsbin.com/medezu/3/

Here is a screenshot:

I am happy to report that a huge number of Object3Ds circ deps have been eliminated. Good job @kumavis!

[kumavis]

wow is that the same codebase? crazy

[ghost]

Will work on making graph generation part of the utility.

[ghost]

On inspection of the graph alone, Shape and Geometry seem to be possible class trees that can be unraveled.

[kumavis]

@coballast think you can take on this?

making the scratch vars in Vector3 Matrix4 defined lazily on first use, not on definition time

[kumavis]

that would be a PR against upstream dev as opposed to an automated change

[kumavis]

Also i think we can downgrade the issue title from "Serious cyclic dependency problems" to "cyclic dependencies" -- situation has much improved!

[ghost]

@kumavis Sure thing. Will work on it when time permits.

[kumavis]

Here is the current state of the interdependency cleanup as i see it: ( arrows show connections that should be removed if appropriate )

• [x] Materials
• [x] Geometries
• [x] Object3D's
• [x] Math
• [x] Shapes
  • [x] Shape -> FontUtils
  • [x] Shape -> ExtrudeGeometry
  • [x] Shape -> ShapeGeometry
  • [x] Path -> Shape
• [ ] Box3
  • [ ] Box3 -> BufferGeometry
  • [ ] Box3 -> Geometry

Shapes:

Box3:

Math:

These nodes are interconnected, but provide sufficient convenience through this.

[ghost]

Shape seems to have dependencies with ExtrudeGeometry and ShapeGeometry through code like this:

// Convenience method to return ExtrudeGeometry

THREE.Shape.prototype.extrude = function ( options ) {

  var extruded = new THREE.ExtrudeGeometry( this, options );
  return extruded;

};

// Convenience method to return ShapeGeometry

THREE.Shape.prototype.makeGeometry = function ( options ) {

  var geometry = new THREE.ShapeGeometry( this, options );
  return geometry;

};

Now it appears Shape is a subclass of Path, and ExtrudeGeometry and ShapeGeometry are both subclasses of Geometry. So, y'know, you can figure out which dependencies would need to go away in the ideal case.