apidom-ls: infinite loop when using `ReferenceValidationMode.APIDOM_INDIRECT_EXTERNAL`

[char0n]

Certain definitions cause infinite loop when language service performs validation with ReferenceValidationMode.APIDOM_INDIRECT_EXTERNAL setting. When changing the setting to ReferenceValidationMode.LEGACY, the validation works as expected.

The traverse function calls lint, which means that traverse is failing to terminate. This indicates possible cycle in provided OpenAPI 3.0.1 definition.

We cannot disclose how the definition looks like here, as it is confidential. It can be found on SmartBear Slack.

Other testing resources:

• https://api.sap.com/odata/1.0/catalog.svc/APIContent.APIs('SAP_ICSM_StudyService')/$value?type=json
• Large response bodies cause hanging swagger-ui#3832

[frantuma]

@char0n This seems to be occurring at apidom-reference level, this branch adds a test in apidom-reference reproducing the issue (I wasn't lucky identifying the root cause..). fixture specs need to be replaced with the problematic definition (currently they have an empty {})

[char0n]

The issue is in mechanism of creating cycles. The definition is so complicated and interconnected that the simple mechanism of creating cycles just isn't enough.

[char0n]

We needed to fix the identity plugins and identity management to properly track element identities during dereferencing: #3840

[char0n]

We needed to address retaining attributes & meta when refracting generic ApiDOM to semantic one: #3842

[char0n]

Dealing with cycles in external definitions in #3863

[char0n]

After researching our options, it has been decided that RefElement will be used to create abstract ApiDOM references. This means that if there are cycles in the definition, we have run full traversal twice to actually create real cycles and transform ApiDOM from directed acyclical tree to directed cyclical graph.

Native support for traversing RefElement will be introduced in #3882

Abstract ApiDOM dereferencing mechanism will be introduced in #3881.

[char0n]

Here is a pseudocode required to detect the cycle and use RefElement to represent it. THis needs to be run before we dive deeper into traversal.

      const mergedElementID = identityManager.generateId(); // this is used to estabilish identity for future transcluded element

      // detect possible cycle in traversal and avoid it
      if (referencingElement.meta.get('cycle')) {
        return { ref: referencingElement.meta.get('refId') };
      }

      // detect second deep dive into the same fragment and avoid it
      if (ancestorsLineage.includes(referencedElement)) {
        referencingElement.meta.set('cycle', true);
        referencingElement.meta.set('refId', mergedElementID);
        reference.circular = true;
        return false;
      }

Here is the version which does introduce the cycles and works 100% on failing swagger-client cases:

    async ReferenceElement(
      referencingElement: ReferenceElement,
      key: any,
      parent: any,
      path: any,
      ancestors: any[],
    ) {
      const [ancestorsLineage, directAncestors] = this.toAncestorLineage([...ancestors, parent]);

      const retrievalURI = this.toBaseURI(toValue(referencingElement.$ref));
      const isInternalReference = url.stripHash(this.reference.uri) === retrievalURI;
      const isExternalReference = !isInternalReference;

      // ignore resolving internal Reference Objects
      if (!this.options.resolve.internal && isInternalReference) {
        // skip traversing this reference element
        return false;
      }
      // ignore resolving external Reference Objects
      if (!this.options.resolve.external && isExternalReference) {
        // skip traversing this reference element
        return false;
      }

      const reference = await this.toReference(toValue(referencingElement.$ref));
      const $refBaseURI = url.resolve(retrievalURI, toValue(referencingElement.$ref));

      this.indirections.push(referencingElement);

      const jsonPointer = uriToPointer($refBaseURI);

      // possibly non-semantic fragment
      let referencedElement = evaluate(jsonPointer, reference.value.result);
      referencedElement.id = identityManager.identify(referencedElement);

      /**
       * Applying semantics to a referenced element if semantics are missing.
       */
      if (isPrimitiveElement(referencedElement)) {
        const referencedElementType = toValue(referencingElement.meta.get('referenced-element'));
        const cacheKey = `${referencedElementType}-${toValue(identityManager.identify(referencedElement))}`;

        if (this.refractCache.has(cacheKey)) {
          referencedElement = this.refractCache.get(cacheKey);
        } else if (isReferenceLikeElement(referencedElement)) {
          // handling indirect references
          referencedElement = ReferenceElement.refract(referencedElement);
          referencedElement.setMetaProperty('referenced-element', referencedElementType);
          this.refractCache.set(cacheKey, referencedElement);
        } else {
          // handling direct references
          const ElementClass = this.namespace.getElementClass(referencedElementType);
          referencedElement = ElementClass.refract(referencedElement);
          this.refractCache.set(cacheKey, referencedElement);
        }
      }

      // detect direct or circular reference
      if (this.indirections.includes(referencedElement)) {
        throw new ApiDOMError('Recursive Reference Object detected');
      }

      // detect maximum depth of dereferencing
      if (this.indirections.length > this.options.dereference.maxDepth) {
        throw new MaximumDereferenceDepthError(
          `Maximum dereference depth of "${this.options.dereference.maxDepth}" has been exceeded in file "${this.reference.uri}"`,
        );
      }

      const mergedElementID = identityManager.generateId();

      /**
       * Dive deep into the fragment.
       *
       * Cases to consider:
       *  1. We're crossing document boundary
       *  2. Fragment is a Reference Object. We need to follow it to get the eventual value
       *  3. We are dereferencing the fragment lazily
       */
      if (isExternalReference || isReferenceElement(referencedElement)) {
        // append referencing reference to ancestors lineage
        directAncestors.add(referencingElement);

        const visitor = OpenApi3_0DereferenceVisitor({
          reference,
          namespace: this.namespace,
          indirections: [...this.indirections],
          options: this.options,
          refractCache: this.refractCache,
          ancestors: ancestorsLineage,
        });
        referencedElement.setMetaProperty('traversed', true);
        referencedElement = await visitAsync(referencedElement, visitor, {
          keyMap,
          nodeTypeGetter: getNodeType,
        });

        // remove referencing reference from ancestors lineage
        directAncestors.delete(referencingElement);
      }

      this.indirections.pop();

      /**
       * Creating a new version of referenced element to avoid modifying the original one.
       */
      const mergedElement = cloneShallow(referencedElement);
      // assign unique id to merged element
      mergedElement.setMetaProperty('id', mergedElementID);
      // annotate referenced element with info about original referencing element
      mergedElement.setMetaProperty('ref-fields', {
        // @ts-ignore
        $ref: toValue(referencingElement.$ref),
      });
      // annotate fragment with info about origin
      mergedElement.setMetaProperty('ref-origin', reference.uri);
      // annotate fragment with info about referencing element
      mergedElement.setMetaProperty(
        'ref-referencing-element-id',
        cloneDeep(identityManager.identify(referencingElement)),
      );

      referencingElement.setMetaProperty('traversed', true);

      /**
       * Transclude referencing element with merged referenced element.
       */
      if (isMemberElement(parent)) {
        parent.value = mergedElement; // eslint-disable-line no-param-reassign
      } else if (Array.isArray(parent)) {
        parent[key] = mergedElement; // eslint-disable-line no-param-reassign
      }

      /**
       * We're at the root of the tree, so we're just replacing the entire tree.
       */
      return !parent ? mergedElement : false;
    },

Here is a version that works with circular = ignore | error | replace

    async ReferenceElement(
      referencingElement: ReferenceElement,
      key: any,
      parent: any,
      path: any,
      ancestors: any[],
    ) {
      const [ancestorsLineage, directAncestors] = this.toAncestorLineage([...ancestors, parent]);

      const retrievalURI = this.toBaseURI(toValue(referencingElement.$ref));
      const isInternalReference = url.stripHash(this.reference.uri) === retrievalURI;
      const isExternalReference = !isInternalReference;

      // ignore resolving internal Reference Objects
      if (!this.options.resolve.internal && isInternalReference) {
        // skip traversing this reference element
        return false;
      }
      // ignore resolving external Reference Objects
      if (!this.options.resolve.external && isExternalReference) {
        // skip traversing this reference element
        return false;
      }

      const reference = await this.toReference(toValue(referencingElement.$ref));
      const $refBaseURI = url.resolve(retrievalURI, toValue(referencingElement.$ref));

      this.indirections.push(referencingElement);

      const jsonPointer = uriToPointer($refBaseURI);

      // possibly non-semantic fragment
      let referencedElement = evaluate(jsonPointer, reference.value.result);
      referencedElement.id = identityManager.identify(referencedElement);

      /**
       * Applying semantics to a referenced element if semantics are missing.
       */
      if (isPrimitiveElement(referencedElement)) {
        const referencedElementType = toValue(referencingElement.meta.get('referenced-element'));
        const cacheKey = `${referencedElementType}-${toValue(identityManager.identify(referencedElement))}`;

        if (this.refractCache.has(cacheKey)) {
          referencedElement = this.refractCache.get(cacheKey);
        } else if (isReferenceLikeElement(referencedElement)) {
          // handling indirect references
          referencedElement = ReferenceElement.refract(referencedElement);
          referencedElement.setMetaProperty('referenced-element', referencedElementType);
          this.refractCache.set(cacheKey, referencedElement);
        } else {
          // handling direct references
          const ElementClass = this.namespace.getElementClass(referencedElementType);
          referencedElement = ElementClass.refract(referencedElement);
          this.refractCache.set(cacheKey, referencedElement);
        }
      }

      // detect direct or circular reference
      if (this.indirections.includes(referencedElement)) {
        throw new ApiDOMError('Recursive Reference Object detected');
      }

      // detect maximum depth of dereferencing
      if (this.indirections.length > this.options.dereference.maxDepth) {
        throw new MaximumDereferenceDepthError(
          `Maximum dereference depth of "${this.options.dereference.maxDepth}" has been exceeded in file "${this.reference.uri}"`,
        );
      }

      // detect second deep dive into the same fragment and avoid it
      if (ancestorsLineage.includes(referencedElement)) {
        if (this.options.dereference.circular === 'error') {
          throw new ApiDOMError('Circular reference detected');
        } else if (this.options.dereference.circular !== 'ignore') {
          const refElement = new RefElement(referencedElement.id, {
            type: 'reference',
            uri: reference.uri,
            $ref: toValue(referencingElement.$ref),
          });
          const replacer =
            this.options.dereference.strategyOpts['openapi-3-0']?.circularReplacer ||
            this.options.dereference.circularReplacer;
          const replacement = replacer(refElement);

          if (isMemberElement(parent)) {
            parent.value = replacement; // eslint-disable-line no-param-reassign
          } else if (Array.isArray(parent)) {
            parent[key] = replacement; // eslint-disable-line no-param-reassign
          }

          reference.refSet.circular = true;

          return !parent ? replacement : false;
        }
      }

      /**
       * Dive deep into the fragment.
       *
       * Cases to consider:
       *  1. We're crossing document boundary
       *  2. Fragment is a Reference Object. We need to follow it to get the eventual value
       *  3. We are dereferencing the fragment lazily
       */
      if (
        isExternalReference ||
        isReferenceElement(referencedElement) ||
        ['error', 'replace'].includes(this.options.dereference.circular)
      ) {
        // append referencing reference to ancestors lineage
        directAncestors.add(referencingElement);

        const visitor = OpenApi3_0DereferenceVisitor({
          reference,
          namespace: this.namespace,
          indirections: [...this.indirections],
          options: this.options,
          refractCache: this.refractCache,
          ancestors: ancestorsLineage,
        });
        referencedElement.setMetaProperty('traversed', true);
        referencedElement = await visitAsync(referencedElement, visitor, {
          keyMap,
          nodeTypeGetter: getNodeType,
        });

        // remove referencing reference from ancestors lineage
        directAncestors.delete(referencingElement);
      }

      this.indirections.pop();

      /**
       * Creating a new version of referenced element to avoid modifying the original one.
       */
      const mergedElement = cloneShallow(referencedElement);
      // assign unique id to merged element
      mergedElement.setMetaProperty('id', identityManager.generateId());
      // annotate referenced element with info about original referencing element
      mergedElement.setMetaProperty('ref-fields', {
        // @ts-ignore
        $ref: toValue(referencingElement.$ref),
      });
      // annotate fragment with info about origin
      mergedElement.setMetaProperty('ref-origin', reference.uri);
      // annotate fragment with info about referencing element
      mergedElement.setMetaProperty(
        'ref-referencing-element-id',
        cloneDeep(identityManager.identify(referencingElement)),
      );

      /**
       * Transclude referencing element with merged referenced element.
       */
      if (isMemberElement(parent)) {
        parent.value = mergedElement; // eslint-disable-line no-param-reassign
      } else if (Array.isArray(parent)) {
        parent[key] = mergedElement; // eslint-disable-line no-param-reassign
      }

      /**
       * We're at the root of the tree, so we're just replacing the entire tree.
       */
      return !parent ? mergedElement : false;
    },

[char0n]

Before utilizing apidom dereference strategy we first need to handle following tickets:

• apidom-reference: use dereference strategies as base of resolution strategies #3452
• apidom-reference: internal vs external resolution #3451

Reasoning: we don't want to maintaint both resolver and dereference strategies and handle cycle detection, etc... Every resolver strategy is technically just a specialization of dereference strategy.

[char0n]

Dereference Architecture has been proposed and documented in #3915