An error occurred (PolicyLengthExceededException) when calling the AddPermission operation
The Policy was not being correctly autogenerated as it did not include DynamoDB permissions, so I added lines manually to .chalice/policy.json, and build using "chalice deploy --no-autogen-policy".

This has been working just fine for the last day, however when deploying now, I'm getting the following error:

**botocore.exceptions.ClientError: An error occurred (PolicyLengthExceededException) when calling the AddPermission operation: The final policy size (20789) is bigger than the limit (20480).**

Nothing has changed in policy.json, and the deploy command was correctly working an hour ago.

I've tried slimming down .chalice/policy.json, but still getting the same error and the same size report (20789).

I've tried deleting the Role from AWS and redeploying.  I then get my .chalice/policy.json shown to me and asked if I want to use it, and I select "y".  The same error is presented.

diff --git a/chalice/awsclient.py b/chalice/awsclient.py
index 4885f7c..25eae0f 100644
--- a/chalice/awsclient.py
+++ b/chalice/awsclient.py
@@ -179,23 +179,112 @@ class TypedAWSClient(object):
         )
         return response
 
+    def add_permission_for_apigateway_if_needed(self, function_name,
+                                                region_name, account_id,
+                                                rest_api_id, random_id):
+        # type: (str, str, str, str, str) -> None
+        """Authorize API gateway to invoke a lambda function is needed.
+
+        This method will first check if API gateway has permission to call
+        the lambda function, and only if necessary will it invoke
+        ``self.add_permission_for_apigateway(...).
+
+        """
+        has_necessary_permissions = False
+        try:
+            policy = self.get_function_policy(function_name)
+        except botocore.exceptions.ClientError as e:
+            error = e.response['Error']
+            if error['Code'] == 'ResourceNotFoundException':
+                pass
+        else:
+            source_arn = self._build_source_arn_str(region_name, account_id,
+                                                    rest_api_id)
+            # Here's what a sample policy looks like after add_permission()
+            # has been previously called:
+            # {
+            #  "Id": "default",
+            #  "Statement": [
+            #   {
+            #    "Action": "lambda:InvokeFunction",
+            #    "Condition": {
+            #     "ArnLike": {
+            #       "AWS:SourceArn": <source_arn>
+            #     }
+            #    },
+            #    "Effect": "Allow",
+            #    "Principal": {
+            #     "Service": "apigateway.amazonaws.com"
+            #    },
+            #    "Resource": "arn:aws:lambda:us-west-2:aid:function:name",
+            #    "Sid": "e4755709-067e-4254-b6ec-e7f9639e6f7b"
+            #   }
+            #  ],
+            #  "Version": "2012-10-17"
+            # }
+            # So we need to check if there's a policy that looks like this.
+            for statement in policy.get('Statement', []):
+                if self._gives_apigateway_access(statement, function_name,
+                                                 source_arn):
+                    has_necessary_permissions = True
+                    break
+        if not has_necessary_permissions:
+            self.add_permission_for_apigateway(
+                function_name, region_name, account_id, rest_api_id, random_id)
+
+    def _gives_apigateway_access(self, statement, function_name, source_arn):
+        # type: (Dict[str, Any], str, str) -> bool
+        if not statement['Action'] == 'lambda:InvokeFunction':
+            return False
+        if statement.get('Condition', {}).get('ArnLike',
+                                              {}).get('AWS:SourceArn',
+                                                      '') != source_arn:
+            return False
+        if statement.get('Principal', {}).get('Service', '') != \\
+                'apigateway.amazonaws.com':
+            return False
+        # We're not checking the "Resource" key because we're assuming
+        # that lambda.get_policy() is returning the policy for the particular
+        # resource in question.
+        return True
+
+    def get_function_policy(self, function_name):
+        # type: (str) -> Dict[str, Any]
+        """Return the function policy for a lambda function.
+
+        This function will extract the policy string as a json document
+        and return the json.loads(...) version of the policy.
+
+        """
+        client = self._client('lambda')
+        policy = client.get_policy(FunctionName=function_name)
+        return json.loads(policy['Policy'])
+
     def add_permission_for_apigateway(self, function_name, region_name,
                                       account_id, rest_api_id, random_id):
         # type: (str, str, str, str, str) -> None
         """Authorize API gateway to invoke a lambda function."""
         client = self._client('lambda')
+        source_arn = self._build_source_arn_str(region_name, account_id,
+                                                rest_api_id)
         client.add_permission(
             Action='lambda:InvokeFunction',
             FunctionName=function_name,
             StatementId=random_id,
             Principal='apigateway.amazonaws.com',
-            SourceArn=('arn:aws:execute-api:{region_name}:{account_id}'
-                       ':{rest_api_id}/*').format(
+            SourceArn=source_arn,
+        )
+
+    def _build_source_arn_str(self, region_name, account_id, rest_api_id):
+        # type: (str, str, str) -> str
+        source_arn = (
+            'arn:aws:execute-api:'
+            '{region_name}:{account_id}:{rest_api_id}/*').format(
                 region_name=region_name,
                 # Assuming same account id for lambda function and API gateway.
                 account_id=account_id,
                 rest_api_id=rest_api_id)
-        )
+        return source_arn
 
     @property
     def region_name(self):
diff --git a/chalice/deployer.py b/chalice/deployer.py
index 74eaa18..fd3e95e 100644
--- a/chalice/deployer.py
+++ b/chalice/deployer.py
@@ -300,7 +300,7 @@ class APIGatewayResourceCreator(object):
                 stack.append(current['children'][child])
         # Add a catch all auth that says anything in this rest API can call
         # the lambda function.
-        self.awsclient.add_permission_for_apigateway(
+        self.awsclient.add_permission_for_apigateway_if_needed(
             self.lambda_arn.split(':')[-1],
             self.region_name,
             self.lambda_arn.split(':')[4],
diff --git a/tests/functional/test_awsclient.py b/tests/functional/test_awsclient.py
index 7eb1107..a28aed5 100644
--- a/tests/functional/test_awsclient.py
+++ b/tests/functional/test_awsclient.py
@@ -339,3 +339,76 @@ class TestCanDeleteRolePolicy(object):
         awsclient = TypedAWSClient(stubbed_session)
         awsclient.delete_role_policy('myrole', 'mypolicy')
         stubbed_session.verify_stubs()
+
+
+class TestAddPermissionsForAPIGateway(object):
+    def test_can_add_permission_for_apigateway(self, stubbed_session):
+        stubbed_session.stub('lambda').add_permission(
+            Action='lambda:InvokeFunction',
+            FunctionName='function_name',
+            StatementId='random-id',
+            Principal='apigateway.amazonaws.com',
+            SourceArn='arn:aws:execute-api:us-west-2:123:rest-api-id/*',
+        ).returns({})
+        stubbed_session.activate_stubs()
+        TypedAWSClient(stubbed_session).add_permission_for_apigateway(
+            'function_name', 'us-west-2', '123', 'rest-api-id', 'random-id')
+        stubbed_session.verify_stubs()
+
+    def should_call_add_permission(self, lambda_stub):
+        lambda_stub.add_permission(
+            Action='lambda:InvokeFunction',
+            FunctionName='name',
+            StatementId='random-id',
+            Principal='apigateway.amazonaws.com',
+            SourceArn='arn:aws:execute-api:us-west-2:123:rest-api-id/*',
+        ).returns({})
+
+    def test_can_add_permission_for_apigateway_needed(self, stubbed_session):
+        # An empty policy means we need to add permissions.
+        lambda_stub = stubbed_session.stub('lambda')
+        lambda_stub.get_policy(FunctionName='name').returns({'Policy': '{}'})
+        self.should_call_add_permission(lambda_stub)
+        stubbed_session.activate_stubs()
+        TypedAWSClient(stubbed_session).add_permission_for_apigateway_if_needed(
+            'name', 'us-west-2', '123', 'rest-api-id', 'random-id')
+        stubbed_session.verify_stubs()
+
+    def test_can_add_permission_for_apigateway_not_needed(self, stubbed_session):
+        source_arn = 'arn:aws:execute-api:us-west-2:123:rest-api-id/*'
+        policy = {
+            'Id': 'default',
+            'Statement': [{
+                'Action': 'lambda:InvokeFunction',
+                'Condition': {
+                    'ArnLike': {
+                        'AWS:SourceArn': source_arn,
+                    }
+                },
+                'Effect': 'Allow',
+                'Principal': {'Service': 'apigateway.amazonaws.com'},
+                'Resource': 'arn:aws:lambda:us-west-2:account_id:function:name',
+                'Sid': 'e4755709-067e-4254-b6ec-e7f9639e6f7b'}],
+            'Version': '2012-10-17'
+        }
+        stubbed_session.stub('lambda').get_policy(
+            FunctionName='name').returns({'Policy': json.dumps(policy)})
+
+        # Because the policy above indicates that API gateway already has the
+        # necessary permissions, we should not call add_permission.
+        stubbed_session.activate_stubs()
+        TypedAWSClient(stubbed_session).add_permission_for_apigateway_if_needed(
+            'name', 'us-west-2', '123', 'rest-api-id', 'random-id')
+        stubbed_session.verify_stubs()
+
+    def test_can_add_permission_when_policy_does_not_exist(self, stubbed_session):
+        # It's also possible to receive a ResourceNotFoundException
+        # if you call get_policy() on a lambda function with no policy.
+        lambda_stub = stubbed_session.stub('lambda')
+        lambda_stub.get_policy(FunctionName='name').raises_error(
+            error_code='ResourceNotFoundException', message='Does not exist.')
+        self.should_call_add_permission(lambda_stub)
+        stubbed_session.activate_stubs()
+        TypedAWSClient(stubbed_session).add_permission_for_apigateway_if_needed(
+            'name', 'us-west-2', '123', 'rest-api-id', 'random-id')
+        stubbed_session.verify_stubs()
diff --git a/tests/unit/test_deployer.py b/tests/unit/test_deployer.py
index 1a072ac..7629a44 100644
--- a/tests/unit/test_deployer.py
+++ b/tests/unit/test_deployer.py
@@ -229,6 +229,7 @@ def test_can_build_resource_routes_for_single_view(stubbed_session):
     ).returns({})
     for error_cls in ALL_ERRORS:
         add_expected_calls_to_map_error(error_cls, gateway_stub)
+    lambda_stub.get_policy(FunctionName='name').returns({'Policy': '{}'})
     lambda_stub.add_permission(
         Action='lambda:InvokeFunction',
         FunctionName='name',
@@ -369,6 +370,7 @@ def test_cors_adds_required_headers(stubbed_session):
             ),
         }
     ).returns({})
+    lambda_stub.get_policy(FunctionName='name').returns({'Policy': '{}'})
     lambda_stub.add_permission(
         Action='lambda:InvokeFunction',
         FunctionName='name',
['tests/unit/test_deployer.py', 'tests/functional/test_awsclient.py', 'chalice/awsclient.py', 'chalice/deployer.py']