Clone Detection for Max/MSP Patch Libraries
Nicolas Gold, Jens Krinke, Mark Harman, David Binkley · 2010
Finding content-based similarities in Max/MSP [1] patches may have a number of useful applications e.g. supporting patch construction and composition or the navigation of large patch collections. We present our current work on detecting similarities in patches written in Max/MSP. The technique we propose is based on clone detection, a well-known approach in software engineering to finding similar and identical pieces of source code within large software systems [2-4]. Dataflow languages such as Max/MSP present particular challenges to existing clone detection technology because of the absence of explicit control flow in the source language. Recent work has addressed this problem for Simulink models [5, 6] but these algorithms are unsuitable for application directly to Max/MSP. Control flow in Max/MSP is dependent on the spatial relationships of the objects used in a patch, thus graph isomorphic approaches such as that of Pham et al. [5] cannot be applied. Our algorithm has three steps. First, patches (in JSON format) are pre-processed to extract information about the Max/MSP objects therein. Sub-patches are not recursively parsed in our current implementation. Second, clone candidates are generated by following paths from the first patch-line found to all linearly-reachable boxes from that path. Patch-lines in cyclic sub-patches are