Relevant Bindings no longer reports shadowed bindings (fixes #12176)
ClosedPublic

Authored by anniecherkaev on Jul 28 2016, 11:48 AM.

Details

Summary

Modified the RelevantBindings method in TcErrors.hs to only search over non-shadowed bindings.

Test Plan

Wrote 2 simple test cases, verified that it worked with multiple shadowed bindings, and also non-shadowed bindings.

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
anniecherkaev retitled this revision from to Relevant Bindings no longer reports shadowed bindings (fixes #12176).
anniecherkaev updated this object.
anniecherkaev edited the test plan for this revision. (Show Details)
anniecherkaev updated the Trac tickets for this revision.
ezyang requested changes to this revision.Jul 28 2016, 12:33 PM
ezyang added a reviewer: ezyang.
ezyang added a subscriber: ezyang.

Short and sweet! :) I have some minor changes to request; but if you like, I can apply the changes myself and merge your patch.

compiler/typecheck/TcErrors.hs
2576

Typo s/buids/builds/, "list of bindings" and s/occurance/occurrence/ (but you could just say OccName instead)

2579

This is quadratic. Better to maintain a OccSet of names we've seen.

2582

Minor stylistic note: when I see get_name, I think this returns a Name; but it returns an OccName: get_occ would be more idiomatic.

Another way you could structure this is to give TcIdBinder a HasOccName instance, and then you could just call occName to retrieve it.

This revision now requires changes to proceed.Jul 28 2016, 12:33 PM

Thanks for the review! I'll implement your suggestions and upload a diff in just a bit. I'll add the HasOccName instance to TcIdBinder- that sounds like a more elegant solution.

anniecherkaev edited edge metadata.
anniecherkaev edited edge metadata.
  • Implemented requested revisions to Trac #12177- Removed unnecessary comment

I implemented your requests, but I have 2 questions: 1) I'm not clear on what the naming convention is- should I be using camel case or underscores? Is it that underscores are used in local functions? What about variable names? 2) I'm not sure that my implementation of the 'remove_shadowing' function is the best approach- I think since I'm passing through an occSet of the names we've seen so far that it should now be n log(n). Please let me know if you think there's a cleaner implementation.

ezyang accepted this revision.Jul 28 2016, 3:40 PM
ezyang edited edge metadata.

LGTM.

  1. I'm not clear on what the naming convention is- should I be using camel case or underscores? Is it that underscores are used in local functions? What about variable names?

My understanding of how code in GHC looks today is: underscores for local variables, "internal" top level functions, record setters; camel-case for top-level "public" functions. But I don't think this is codified anywhere.

  1. I'm not sure that my implementation of the 'remove_shadowing' function is the best approach- I think since I'm passing through an occSet of the names we've seen so far that it should now be n log(n). Please let me know if you think there's a cleaner implementation.

n log(n) is fine. Honestly, n^2 is probably OK too (these binding lists shouldn't get too long) but I like getting rid of easily killed quadratics if I can on principle.

This revision is now accepted and ready to land.Jul 28 2016, 3:40 PM

Hey- I don't know if it's too late or too much hassel to change anything now, but I just thought of the solution I was looking for yesterday- replace that 5 line remove_shadowing function:

reverse $ fst $ foldl
      (\(bindingAcc, seenNames) binding ->
        if (occName binding) `elemOccSet` seenNames -- if we've seen it
          then (bindingAcc, seenNames)              -- skip it
          else (binding:bindingAcc, extendOccSet seenNames (occName binding)))

with

nubBy (\x y -> (occName x) == (occName y)) bindings

I reran the tests, and they all still pass, I'm pretty sure it's the same behavior. I also realize that since I was reversing the list (so that the inner-most bindings remain first) in that top implementation the performance was actually probably n^2 log n... And this way with nubBy it would be n^2. I can generate a new diff if you'd like, or just leave it be, please let me know what you think would be best.

Hmm, am I misunderstanding? What you had previously should only be n log n, because the reverse is just a flat linear cost.

Oh! Yes, you're right, my mistake!

This revision was automatically updated to reflect the committed changes.