Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

One of the recent features of the Mathematica Plugin for IntelliJ IDEA (www.mathematicaplugin.halirutan.de) is a Structure View which let's you see information about several definitions that are done in a source file. It currently looks like the left side of the image below:

enter image description here

To provide such a feature, I need to extract which symbol is set when the user uses things like

  • lhs = rhs or lhs := rhs
  • s /: patt = rhs or s /: patt := rhs
  • lhs ^= rhs or lhs ^:= rhs
  • Options[sym] = rhs, Attributes[sym] = rhs, SyntaxInformation[sym] = lhs, Format[sym] ] = rhs, N[sym] = rhs, Default[sym] = rhs
  • sym::tag = rhs

Since in IDEA I cannot evaluate code like one can in Mathematica, I have to extract all those information from inspecting the abstract syntax tree (TreeForm in Mathematica). For this, I have a so-called visitor which walks through the tree and collects information. One can easily write such a visitor (or expression parser) in Mathematica itself. I have written a very basic version of such a visitor, which takes a expression like f[x_]:=x^2 and extracts the symbols which is set and the type of the assignment. Partly, I have simply copied code from Leonids answer here. Before giving the code here are my

Questions: Can the visitor below be improved? Are there missing cases, things I haven't thought of, things that don't work correctly? Especially UpSet is interesting because there, more than one symbol can be set at the same time.


Here is a very basic visitor which uses simple pattern matching to check the structure of an expression:

ClearAll[visit];
SetAttributes[visit, {HoldAllComplete}];
visit[s_Symbol] := MakeBoxes[s];
visit[(h : (SetDelayed | Set))[lhs_, _]] := {MakeBoxes[h], visit[lhs]};
visit[(h : (TagSetDelayed | TagSet))[a_, _, _]] := {MakeBoxes[h], visit[a]};
visit[(h : (UpSetDelayed | UpSet))[_[args__], _]] := {MakeBoxes[h], visit[args]};
visit[HoldPattern[Options[sym_] = _]] := {MakeBoxes[Options], visit[sym]};
visit[HoldPattern[Attributes[sym_] = _]] := {MakeBoxes[Attributes], visit[sym]};
visit[HoldPattern[SetAttributes[sym_, _]]] := {MakeBoxes[Attributes], visit[sym]};
visit[HoldPattern[SyntaxInformation[sym_] = _]] := {MakeBoxes[SyntaxInformation], visit[sym]};
visit[HoldPattern[Default[sym_] = _]] := {MakeBoxes[DefaultValues], visit[sym]};
visit[HoldPattern[MessageName[sym_, tag_] = _]] := {MakeBoxes[Messages], visit[sym], MakeBoxes[tag]};
visit[Verbatim[Format][sym_] := _] := {MakeBoxes[FormatValues], visit[sym]};
visit[HoldPattern[(Set | SetDelayed)[N[sym_], _]]] := {MakeBoxes[NValues], visit[sym]};

visit[(Condition | PatternTest | Optional)[arg_, _]] := visit[arg];
visit[(HoldPattern | Optional)[arg_]] := $Failed;
visit[Verbatim[Pattern][sym_, _]] := $Failed
visit[Verbatim[Repeated][p_, ___]] := $Failed;
visit[(Blank | BlankSequence | BlankNullSequence)[___]] := $Failed;
visit[(Longest | Shortest)[arg_, ___]] := $Failed;
visit[Verbatim[PatternSequence][args___]] := $Failed;
visit[a_ /; AtomQ[Unevaluated[a]]] := $Failed;
visit[args___] := List @@ Map[visit, Hold[args]];
visit[f_[args___]] := visit[f];

SetAttributes[StructureView, {HoldAll}];
StructureView[sets_Hold] := Column[List @@ Map[visit, sets]]

And here are some positive test-cases that work

StructureView[Hold[
  f[x_] := x^2,
  SetAttributes[sym, {HoldAll}],
  Options[Plot] = {PlotRange -> Automatic},
  square /: area[square] = a^2,
  area[rectangle] ^= a*b,
  int /: rand[int] = Random[Integer],
  h /: f[h[x_]] = x^2,
  SyntaxInformation[
    f] = {"ArgumentsPattern" -> {_, _, OptionsPattern[]}},
  N[f[x_]] := Sum[x^-i/i^2, {i, 20}],
  f::usage = "f[x] gives (x - 1)(x + 1)",
  area[square1, square2] ^= s^2,
  Format[bin[x_, y_]] := MatrixForm[{{x}, {y}}]]]

And here are some test-cases that (correctly) fail because they are semantically not valid

StructureView[Hold[
  h_ /: f[h[x_]] = x^2,
  f_[x] := x^2,
  f_[x_] := x^2,
  "f"[x_] := x
  ]]

Final notes

  • I haven't included vector-set like {a,b}={1,2} and the special notation a[[1]]=4 on purpose.
  • I someone doesn't want to post a complete answer, but wants to discuss something, then ping me in the plugin chatroom
share|improve this question
    
Humm, there's the manual way of defining XValues[sym]={lalalla} for all DownValues, OwnValues etc. –  Rojo Jun 23 at 7:59
    
Also you could DeleteDuplicates on List @@ Map[visit, Hold[args]] –  Rojo Jun 23 at 8:02
    
Also, even though automatic reordering happens, it may be nicer to put the definitions of general Set and SetDelayed at the end –  Rojo Jun 23 at 8:04
    
Perhaps Options and the others can be defined with := as well as =. Why do you choose to make Condition and PatternTest fail? –  Rojo Jun 23 at 8:17

1 Answer 1

Here is the functionality I wrote as a part of the static code analyzer, which itself is a part of my effort to construct a FE-based IDE. It takes into account variable localization, and gives only globally-defined symbols, defined in a given piece of code.

Some helper functions:

ClearAll[shead];
SetAttributes[shead, HoldAllComplete];
shead[f_Symbol[___]] := HoldComplete[f];
shead[f_[___]] := shead[f];
shead[f_ /; AtomQ[Unevaluated[f]]] := Head[f];

(* TODO: This is a bit too simplisitc, since some pattern symbols \    
might be localized by inner rules inside expr, and should not be \
counted. We might miss some extra dependencies this way *)

ClearAll[getPatternSymbols];
SetAttributes[getPatternSymbols, HoldAllComplete];
getPatternSymbols[expr_] :=
  Cases[
    Unevaluated[expr],
    Verbatim[Pattern][ss_, _] :> HoldComplete[ss],
    {0, \[Infinity]},
    Heads -> True
  ];

ClearAll[getDeclaredSymbols];
SetAttributes[getDeclaredSymbols, HoldAllComplete];
getDeclaredSymbols[{decs___}]:=
  Thread[
    Replace[
      HoldComplete[{decs}],
      HoldPattern[a_=rhs_] :> a,
      {2}
    ]
  ];

getDeclaredSymbols[_]={};


ClearAll[getDeclarationRHSides];
SetAttributes[getDeclarationRHSides, HoldAllComplete];
getDeclarationRHSides[{decs___}]:=
  Cases[
    Unevaluated[{decs}],
    Verbatim[Set][_ , rhs_]:>HoldComplete[rhs],
    {1}
  ];

getDeclarationRHSides[_]:={};


ClearAll[extractSymbolsForUpValues];
SetAttributes[extractSymbolsForUpValues, HoldAllComplete];
extractSymbolsForUpValues[args___] :=
  DeleteCases[
    Cases[
      HoldComplete[args], 
      s_Symbol :> HoldComplete[s], 
      {-1}, 
      Heads -> True
    ],
    HoldComplete[HoldComplete]
  ];

The main implementation:

ClearAll[definesExt, filter, $defaultExcludes, defInfo];

$defaultExcludes = {HoldComplete[Condition]};

SetAttributes[filter, HoldAllComplete];
filter[sym_Symbol, excluded_]:= filter[HoldComplete[sym], excluded];
filter[held_HoldComplete, excluded_]:= Complement[{held}, excluded];


SetAttributes[definesExt,HoldAllComplete];

definesExt[Verbatim[Unevaluated][expr_],excluded_]:=
definesExt[expr,excluded];

definesExt[
Set[
      (prop: Alternatives[
               Options,
               Attributes,
               DefaultValues,
               OwnValues,
               DownValues,
               SubValues,
               UpValues,
               NValues,
               FormatValues,
               Messages
       ])[sym_Symbol]
       ,
       rhs_], excluded_]:= 
 Join[
   {defInfo[filter[sym,excluded],prop]},
   definesExt[rhs, excluded]
 ];

definesExt[Unset[sym_Symbol],excluded_]:= 
   List @ defInfo[filter[sym,excluded],Unset];

definesExt[(h:(Clear|ClearAll|Remove))[syms__Symbol], excluded_]:=
   List @ defInfo[
     Complement[
        Thread @ HoldComplete[{syms}],
        excluded
     ],
     h
   ];


definesExt[Set[MessageName[sym_,_],rhs_], excluded_]:=
  Join[
    {defInfo[filter[sym,excluded],MessageName]},
    definesExt[rhs, excluded]
  ];

definesExt[
  (h:(Set | SetDelayed | UpSet | UpSetDelayed))[
     Verbatim[Condition][lhs_, cond_], rhs_
  ],
  excluded_
]:=
  With[{excl = Join[excluded, getPatternSymbols[lhs]]},
    Join[
      definesExt[h[lhs,rhs], excluded],
      definesExt[cond, excl]
    ]
  ];


definesExt[
   (h:(TagSet|TagSetDelayed))[tag_Symbol, Verbatim[Condition][lhs_,cond_], rhs_],
    excluded_
]:=
  With[{excl = Join[excluded, getPatternSymbols[lhs]]},
    Join[
      definesExt[h[tag, lhs, rhs], excluded],
      definesExt[cond, excl],
      {defInfo[filter[tag, excluded],h]}
    ]
  ];

definesExt[(h:(Set|SetDelayed))[lhs_Symbol,rhs_], excluded_]:=
  With[{excl=Join[excluded, getPatternSymbols[lhs]]},
    With[{exclFinal = If[h===Set,excluded,excl]},
      Join[
        {defInfo[filter[lhs,excluded],h]},
        definesExt[rhs,exclFinal]
      ]
    ]
  ];


(* TODO: We need a more general parsing scheme for this type of patterns *)

definesExt[
   (h:(Set|SetDelayed))[Verbatim[Pattern][name_Symbol,body_],rhs_],
   excluded_
]:=
  With[{excl = Join[excluded,HoldComplete[name]]},
    definesExt[h[body,rhs], excl]
  ];

definesExt[
  (h:(Set|SetDelayed))[
      (head: Verbatim[Pattern][name_Symbol,body_])[args___],
      rhs_
  ], 
  excluded_
]:=
  With[{excl = Join[excluded,{HoldComplete[name]}]},
    definesExt[h[body[args],rhs], excl]
  ]

definesExt[(h:(Set|SetDelayed))[lhs_,rhs_], excluded_]:=
  With[{
    excl=Join[excluded, getPatternSymbols[lhs]],
    head = shead[lhs]
    },
    With[{exclFinal = If[h===Set,excluded,excl]},
      Join[
         definesExt[lhs,excl],
         definesExt[rhs,exclFinal],
         {defInfo[filter[head,excluded],h]}
      ]
    ] /; MatchQ[head,_HoldComplete]
  ];

definesExt[_SetDelayed | _Set, _]:=
   Throw[$Failed, {definesExt, SetDelayed|Set}];

definesExt[(h:(UpSet | UpSetDelayed))[lhs:f_[args___],rhs_],excluded_]:=
  With[{excl = Join[excluded, getPatternSymbols[lhs]]},
    With[{exclFinal = If[h === UpSet,excluded,excl]},
      Join[
        definesExt[lhs,excl],
        definesExt[rhs,exclFinal], 
        {defInfo[Complement[extractSymbolsForUpValues[args], excluded],h]}
      ]
    ]
  ];

definesExt[(h:(TagSet|TagSetDelayed))[tag_Symbol, lhs_, rhs_], excluded_]:=
  With[{excl = Join[excluded, getPatternSymbols[lhs]]},
    With[{exclFinal = If[h === TagSet,excluded,excl]},
      Join[
        definesExt[lhs, excl],
        definesExt[rhs,exclFinal],
        {defInfo[filter[tag, excluded],h]}
      ]
    ]
  ];

definesExt[SetOptions[sym_Symbol,rhs_],excluded_]:= 
  Join[
    {defInfo[filter[sym, excluded],SetOptions]},
    definesExt[rhs, excluded]
  ]

definesExt[SetAttributes[{syms___Symbol},rhs_], excluded_]:=
  Join[
    List @ defInfo[
      Map[
        Function[s,filter[s, excluded],HoldAllComplete],
        Unevaluated[{syms}]
      ],
      SetAttributes
    ],
    definesExt[rhs, excluded]
  ];

definesExt[SetAttributes[sym_Symbol,rhs_], excluded_]:=
  Join[
    {defInfo[filter[sym, excluded],SetAttributes]},
    definesExt[rhs, excluded]
  ];

definesExt[Verbatim[Pattern][_,body_], excluded_]:=
  definesExt[body, excluded];

definesExt[Verbatim[Condition][expr_,cond_],excluded_]:=
  With[{excl=Join[excluded, getPatternSymbols[expr]]},
    Join[
      definesExt[expr, excl],
      definesExt[cond, excl]
    ]
  ]

definesExt[Verbatim[PatternTest][patt_Pattern, fun_], excluded_]:=
  Join[
    definesExt[patt, excluded],
    definesExt[fun, excluded]
  ];

definesExt[Function[Null,body_,atts_], excluded_]:=
  definesExt[body, excluded];

definesExt[body_&, excluded_]:= 
  definesExt[body, excluded];

definesExt[Function[var_,body_], excluded_]:=
  definesExt[Function[{var},body], excluded];

definesExt[Function[{vars__},body_], excluded_]:=
  With[{excl = Join[excluded, Thread[HoldComplete[{vars}]]]},
    definesExt[body, excl]
  ];

(* TODO: the Block case is not clear-cut, whether to include it *)
definesExt[(With | Module | Block)[decs_,body_], excluded_]:=
  With[{rhsides = getDeclarationRHSides[decs]},
    With[{joined = Join[excluded, getDeclaredSymbols[decs]]},
      Join[
        definesExt[body, joined],
        definesExt[rhsides, excluded]
      ]
    ]
  ];

definesExt[f_[elems___], excluded_]:=
  Join[
    definesExt[Unevaluated[f], excluded],
    Sequence @@ Map[
      Function[arg, definesExt[arg, excluded], HoldAllComplete],
      Unevaluated[{elems}]
    ]
  ];

definesExt[a_ /; AtomQ[Unevaluated[a]], _]:={};

definesExt[code_]:=
   With[{excl = $defaultExcludes}, 
     definesExt[code, excl]
   ];

definesExt[args___]:=Throw[$Failed, {definesExt, Hold[args]}];

The main idea is that the function maintains a list of currently local symbols, as its second argument. This list gets augmented by symbols localized in a given scoping construct, when the analysis "goes through" this construct. In this way, we exclude localized symbols from the analysis, precisely for the scope where they are localized.

The public function:

ClearAll[definesFull];
SetAttributes[definesFull, HoldAllComplete];
definesFull[expr_]:=
  Composition[
    Map[{First@First@#,Tally@#[[All,2]]}&],
    GatherBy[#,First]&,
    Flatten[#,1]&,
    Composition[Thread, List] @@@ #&
  ] @ DeleteCases[definesExt[expr],defInfo[{},_]];

The definesExt function gives a more detailed information, while definesFull computes frequencies of various assignment operators for all assignments for a given symbol, in this piece of code.

I have tested this functionality rather extensively, since it was used for static analysis of large projects (thousands of lines of code, multiple files). Still, it is most certainly incomplete / contains some bugs.

The main possible advantage of this code is that it takes into account variable localization in scoping constructs. Still, the possible disadvantages here is that it does not report assignments to localized variables and functions (intentionally).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.