AdtMemberTraitValidator is a bit slow

In a model with a lot of member shapes, AdtMemberTraitValidator is increasingly slow. This is a problem because validators run on every didChange notification in the LSP, which can slow down your editor experience a lot (e.g. formatting will have to wait for this as well, assuming the current implementation).

I see one obvious culprit: in AdtValidatorCommon, every time getReferences is called, it iterates over all member shapes of the model. This happens for each @adt and each @adtMember target.

Here's the relevant code:

    private static List<Reference> getReferences(Model model, Shape adtMemberShape, Shape adtParent) {
        return model.getMemberShapes().stream().flatMap(memberShape -> {
            boolean doesMemberTargetAdtShape = memberShape.getTarget() == adtMemberShape.getId();
            boolean isMemberShapeInDesiredTarget = memberShape.getContainer().equals(adtParent.toShapeId());
            if (doesMemberTargetAdtShape) {
                return Stream.of(new Reference(isMemberShapeInDesiredTarget, memberShape.getContainer()));
            } else {
                return Stream.empty();
            }
        }).collect(Collectors.toList());
    }

Perhaps we can have a quick win by pre-computing a map of member shapes whose target passes certain criteria. At first sight I'm not sure how to formulate that criteria in an efficient way though, so this needs some more careful inspection.

For reference, the models I'm concerned about have roughly 25k member shapes, and that number isn't going down anytime soon.

At the moment, on my machine it takes ~1000-1200ms for a single run of AdtMemberTraitValidator. AdtTraitValidator is noticeably faster (~100ms). This is calculated with nanoTime().

Some profiler output:

(yeah, it shows less than 600ms here, which is much better, but a suspicious score nevertheless)

disneystreaming / smithy4s

AdtMemberTraitValidator is a bit slow #1319