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}]})}