Unravelled/PathFinder — pull request #20 by gregsexton (2014-09-06 15:23:59+00:00)
Title: Extract function usages

Hey guys,

This extracts from clojure source the interesting function usages. Interesting here is defined to be either a function that was explicitly required in the ns declaration or was defined within this file. Took me way longer than I thought it would to get this working! Let me know what you think.

Here's an example output, running it for the clojure.clj file:

pathfinder.analyze.clojure> (r/analyze (->CljHeuristicAnalyzer) *1 {})
{:meta {},
:source
"(ns pathfinder.analyze.clojure\n (:require [clojure.string :as str]\n [clojure.tools.analyzer.jvm :as jvm-analyzer]\n [clojure.tools.reader :as reader]\n [clojure.tools.reader.reader-types :as readers]\n [pathfinder.analyze.analyzer :refer [Analyzer]]))\n\n(defmacro def- [symbol init?]\n `(def ^:private ~symbol ~init?))\n\n;; TODO: arbitrary code can be executed during read (and obviously\n;; evaluation) of clojure code. Currently, these analyzers should only\n;; be used for trusted source. We should look in to sandboxing this\n;; process and probably killing it after a timeout.\n\n(defn- read-forms [source]\n (let [pbr (readers/indexing-push-back-reader source)\n eof (Object.)]\n (take-while #(not (identical? % eof))\n (repeatedly #(reader/read pbr false eof)))))\n\n(defn- extract-data-model [ast meta])\n\n;; TODO: using jvm-analyzer we can do a full parse and build a\n;; complete, perfectly accurate, ast. This is essentially the front half\n;; of the clojure compiler. It would imply loading code in at the\n;; granularity of a project. We would probably need to understand the\n;; build system too. For now I've hacked up a fairly basic parser based\n;; on heuristics, see CljHeuristicAnalyzer below.\n\n(deftype CljAnalyzer []\n Analyzer\n (analyze [this source meta]\n (-> source\n read-forms\n (->> (map jvm-analyzer/analyze))\n #_(extract-data-model meta))))\n\n(defn extract-pos-from-meta [form]\n (select-keys (meta form) [:column :line :end-column :end-line]))\n\n(defn- prefix-spec? [form]\n (and (sequential? form) ; should be a list, but often is not\n (symbol? (first form))\n (not-any? keyword? form)\n (< 1 (count form)))) ; not a bare vector like [foo]\n\n(defn- option-spec? [form]\n (and (sequential? form) ; should be a vector, but often is not\n (symbol? (first form))\n (or (keyword? (second form)) ; vector like [foo :as f]\n (= 1 (count form))))) ; bare vector like [foo]\n\n(defn- reduce-libspecs [option-reducer]\n (fn help\n ([libspecs] (help nil libspecs))\n ([prefix libspecs]\n (reduce (fn [acc spec]\n (cond (prefix-spec? spec) (help (first spec) (rest spec))\n (option-spec? spec) (option-reducer acc prefix spec)\n :else acc))\n []\n libspecs))))\n\n(def- find-aliases\n (reduce-libspecs (fn [acc prefix spec]\n (concat acc\n (map vector (->> (rest spec)\n (partition 2)\n (filter #(= :as (first %)))\n (map second))\n (repeat (str (when prefix (str prefix \".\"))\n (first spec))))))))\n\n(def- find-refers\n (reduce-libspecs (fn [acc prefix spec]\n (->> (rest spec)\n (partition 2)\n (filter #(= :refer (first %)))\n (mapcat second)\n (map (fn [f] [f (str (when prefix (str prefix \".\"))\n (first spec) \"/\" f)]))\n (concat acc)))))\n\n(defn- extract-require-forms [coll]\n (->> coll\n (filter #(and (list? %) (= :require (first %))))\n (mapcat rest)))\n\n(defn- extract-ns [state form]\n (if (and (list? form) (= (first form) 'ns))\n (let [require-forms (extract-require-forms form)]\n (assoc state :ns\n {:name (second form)\n :aliases (into {} (find-aliases require-forms))\n :refers (into {} (find-refers require-forms))}))\n state))\n\n(defn- extract-definition [state form]\n ;; support only the clojure.core types for now\n (let [types '{def :definition\n definline :function\n definterface :interface\n defmacro :macro\n defmethod :method\n defmulti :multimethod\n defn :function\n defn- :function\n defprotocol :protocol\n defrecord :record\n defstruct :struct\n deftype :class}]\n (if (and (list? form) (.startsWith (str (first form)) \"def\")) ;crude\n (let [ns (get-in state [:ns :name])]\n (update-in state [:model :definitions]\n conj {:name (str ns (if ns \"/\" \"\") (second form))\n :type (get types (first form) :unknown)\n :pos (extract-pos-from-meta form)}))\n state)))\n\n(defn- merge-with-key\n \"Merge maps with a common scalar key. All other values should be\n seqs.\"\n [key maps]\n (->> maps\n (group-by key)\n (map (fn [[key-value maps]]\n (->> maps\n (map #(dissoc % key))\n (apply merge-with concat)\n (#(assoc % key key-value)))))))\n\n(defn- find-usages [interesting-usage? build-usage form]\n (letfn [(reduce-form [form]\n (when (list? form)\n (cond\n (empty? form) nil\n (= (first form) 'quote) nil\n :else (if (interesting-usage? (first form))\n (cons (build-usage (first form)) (mapcat reduce-form (rest form)))\n (mapcat reduce-form (rest form))))))]\n (reduce-form form)))\n\n(defn- split-f-name [f-name] (str/split (str f-name) #\"/\" 2))\n\n(defn- build-usage [ns]\n (fn [f-name]\n (let [name (split-f-name f-name)\n resolved-name (if (= (count name) 2)\n (str (get (:aliases ns) (symbol (first name))) \"/\" (second name))\n (get (:refers ns) (symbol (first name))\n ;; if not a referred fn then must be defined in this ns\n (str (:name ns) \"/\" (first name))))]\n {:name resolved-name\n :pos [(extract-pos-from-meta f-name)]})))\n\n(defn- explicitly-required [ns]\n (fn [f-name]\n (let [name (split-f-name f-name)]\n (if (= (count name) 2)\n (contains? (:aliases ns) (symbol (first name)))\n (contains? (:refers ns) (symbol (first name)))))))\n\n(defn- defined-in-ns [definitions]\n (fn [f-name]\n (let [lookup (->> definitions\n (map (comp second split-f-name :name))\n (into #{}))]\n (lookup (str f-name)))))\n\n(defn- any [& fns]\n (fn [x]\n (reduce #(or %1 (%2 x)) false fns)))\n\n(defn- extract-usages [state form]\n (update-in state [:model :usages] (comp (partial merge-with-key :name) concat)\n (find-usages (any (explicitly-required (:ns state))\n (defined-in-ns (get-in state [:model :definitions])))\n (build-usage (:ns state))\n form)))\n\n(defn- guess-data-model [forms]\n (->> forms\n (reduce (fn [state form]\n (-> state\n (extract-ns form)\n (extract-definition form)\n (extract-usages form)))\n {:ns nil :model {}})\n :model))\n\n(deftype CljHeuristicAnalyzer []\n ;; guess without full parse and eval context\n Analyzer\n (analyze [this source meta]\n (-> source\n read-forms\n guess-data-model\n (merge {:source source\n :meta meta}))))\n",
:definitions
({:name "pathfinder.analyze.clojure/CljHeuristicAnalyzer",
:type :class,
:pos {:end-line 200, :end-column 32, :line 192, :column 1}}
{:name "pathfinder.analyze.clojure/guess-data-model",
:type :function,
:pos {:end-line 190, :end-column 16, :line 182, :column 1}}
{:name "pathfinder.analyze.clojure/extract-usages",
:type :function,
:pos {:end-line 180, :end-column 34, :line 175, :column 1}}
{:name "pathfinder.analyze.clojure/any",
:type :function,
:pos {:end-line 173, :end-column 41, :line 171, :column 1}}
{:name "pathfinder.analyze.clojure/defined-in-ns",
:type :function,
:pos {:end-line 169, :end-column 31, :line 164, :column 1}}
{:name "pathfinder.analyze.clojure/explicitly-required",
:type :function,
:pos {:end-line 162, :end-column 59, :line 157, :column 1}}
{:name "pathfinder.analyze.clojure/build-usage",
:type :function,
:pos {:end-line 155, :end-column 49, :line 146, :column 1}}
{:name "pathfinder.analyze.clojure/split-f-name",
:type :function,
:pos {:end-line 144, :end-column 62, :line 144, :column 1}}
{:name "pathfinder.analyze.clojure/find-usages",
:type :function,
:pos {:end-line 142, :end-column 25, :line 133, :column 1}}
{:name "pathfinder.analyze.clojure/merge-with-key",
:type :function,
:pos {:end-line 131, :end-column 51, :line 121, :column 1}}
{:name "pathfinder.analyze.clojure/extract-definition",
:type :function,
:pos {:end-line 119, :end-column 15, :line 99, :column 1}}
{:name "pathfinder.analyze.clojure/extract-ns",
:type :function,
:pos {:end-line 97, :end-column 12, :line 90, :column 1}}
{:name "pathfinder.analyze.clojure/extract-require-forms",
:type :function,
:pos {:end-line 88, :end-column 23, :line 85, :column 1}}
{:name "pathfinder.analyze.clojure/find-refers",
:type :unknown,
:pos {:end-line 83, :end-column 43, :line 75, :column 1}}
{:name "pathfinder.analyze.clojure/find-aliases",
:type :unknown,
:pos {:end-line 73, :end-column 67, :line 65, :column 1}}
{:name "pathfinder.analyze.clojure/reduce-libspecs",
:type :function,
:pos {:end-line 63, :end-column 28, :line 54, :column 1}}
{:name "pathfinder.analyze.clojure/option-spec?",
:type :function,
:pos {:end-line 52, :end-column 33, :line 48, :column 1}}
{:name "pathfinder.analyze.clojure/prefix-spec?",
:type :function,
:pos {:end-line 46, :end-column 28, :line 42, :column 1}}
{:name "pathfinder.analyze.clojure/extract-pos-from-meta",
:type :function,
:pos {:end-line 40, :end-column 67, :line 39, :column 1}}
{:name "pathfinder.analyze.clojure/CljAnalyzer",
:type :class,
:pos {:end-line 37, :end-column 39, :line 31, :column 1}}
{:name "pathfinder.analyze.clojure/extract-data-model",
:type :function,
:pos {:end-line 22, :end-column 38, :line 22, :column 1}}
{:name "pathfinder.analyze.clojure/read-forms",
:type :function,
:pos {:end-line 20, :end-column 61, :line 16, :column 1}}
{:name "pathfinder.analyze.clojure/def-",
:type :macro,
:pos {:end-line 9, :end-column 35, :line 8, :column 1}}),
:usages
({:name "pathfinder.analyze.clojure/any",
:pos [{:end-line 177, :end-column 32, :line 177, :column 28}]}
{:name "pathfinder.analyze.clojure/def-",
:pos
({:end-line 65, :end-column 7, :line 65, :column 2}
{:end-line 75, :end-column 7, :line 75, :column 2})}
{:name "pathfinder.analyze.clojure/extract-ns",
:pos [{:end-line 186, :end-column 34, :line 186, :column 23}]}
{:name "pathfinder.analyze.clojure/extract-definition",
:pos [{:end-line 187, :end-column 42, :line 187, :column 23}]}
{:name "pathfinder.analyze.clojure/explicitly-required",
:pos [{:end-line 177, :end-column 53, :line 177, :column 33}]}
{:name "pathfinder.analyze.clojure/option-spec?",
:pos [{:end-line 60, :end-column 38, :line 60, :column 25}]}
{:name "pathfinder.analyze.clojure/defined-in-ns",
:pos [{:end-line 178, :end-column 47, :line 178, :column 33}]}
{:name "pathfinder.analyze.clojure/extract-usages",
:pos [{:end-line 188, :end-column 38, :line 188, :column 23}]}
{:name "clojure.string/split",
:pos [{:end-line 144, :end-column 41, :line 144, :column 31}]}
{:name "pathfinder.analyze.clojure/prefix-spec?",
:pos [{:end-line 59, :end-column 38, :line 59, :column 25}]}
{:name "pathfinder.analyze.clojure/find-usages",
:pos [{:end-line 177, :end-column 27, :line 177, :column 15}]}
{:name "clojure.tools.reader/read",
:pos [{:end-line 20, :end-column 43, :line 20, :column 31}]}
{:name "pathfinder.analyze.clojure/reduce-libspecs",
:pos
({:end-line 66, :end-column 20, :line 66, :column 4}
{:end-line 76, :end-column 20, :line 76, :column 4})}
{:name "pathfinder.analyze.clojure/build-usage",
:pos [{:end-line 179, :end-column 40, :line 179, :column 28}]})}