Repository: solid/community-server (ts)

Issue:
Create AutomaticConvertor to automatically chain the correct convertors
Currently, this is the configuration I need to support `GET`, `PUT`, and `PATCH` with a custom JSON format is: https://github.com/RubenVerborgh/solid-hue/blob/bd4fcd864ef89d348017891834ff75056e077aed/config/config-hue.json#L71-L90

```json
    {
      "@id": "solid-hue:RepresentationConverter",
      "@type": "WaterfallHandler",
      "WaterfallHandler:_handlers": [
        { "@type": "HueToQuadConverter" },
        { "@type": "QuadToHueConverter" },
        {
          "@id": "solid-hue:HueToRdfConverter",
          "@type": "ChainedConverter",
          "ChainedConverter:_converters": [
            { "@type": "HueToQuadConverter" },
            { "@id": "solid-server:QuadToRdfConverter" }
          ]
        },
        {
          "@id": "solid-hue:RdfToHueConverter",
          "@type": "ChainedConverter",
          "ChainedConverter:_converters": [
            { "@id": "solid-server:RdfToQuadConverter" },
            { "@type": "QuadToHueConverter" }
          ]
        }
      ]
    }
```

This is because the `ChainedConvertor` can only execute the exact chain.

Instead, I'd like to

```json
    {
      "@id": "solid-hue:RepresentationConverter",
      "@type": "MatrixConverter",
      "MatrixConverter:_converter": [
        { "@type": "HueToQuadConverter" },
        { "@type": "QuadToHueConverter" },
        { "@id": "solid-server:QuadToRdfConverter" },
        { "@id": "solid-server:RdfToQuadConverter" }
      ]
    }
```

with a `MatrixConverter` that finds the needed path itself per request at runtime.

Pull request description:
feat: Update ChainedConverter to create dynamic paths
Closes #484, see discussion there as well.

Instead of creating a new class I updated `ChainedConverter` since we would have no need for that one anymore after this.

The `canHandle` call of this one is going to be more expensive than most other classes, but this should always be the last handler that gets checked so this should be fine.

There are some parts that could be move to separate files: the cache could be a separate class file, some functions could be moved to `ConversionUtil`, but they are very specific to this implementation so it made sense to me to keep them there.

Patch:
diff --git a/config/presets/representation-conversion.json b/config/presets/representation-conversion.json
index 475985938..6f51fbec0 100644
--- a/config/presets/representation-conversion.json
+++ b/config/presets/representation-conversion.json
@@ -91,12 +91,6 @@
         {
           "@id": "urn:solid-server:default:ContentTypeReplacer"
         },
-        {
-          "@id": "urn:solid-server:default:RdfToQuadConverter"
-        },
-        {
-          "@id": "urn:solid-server:default:QuadToRdfConverter"
-        },
         {
           "@id": "urn:solid-server:default:RdfRepresentationConverter"
         }
diff --git a/src/storage/conversion/ChainedConverter.ts b/src/storage/conversion/ChainedConverter.ts
index fc6de1298..fda7125ea 100644
--- a/src/storage/conversion/ChainedConverter.ts
+++ b/src/storage/conversion/ChainedConverter.ts
@@ -1,89 +1,297 @@
 import type { Representation } from '../../ldp/representation/Representation';
+import type { ValuePreference, ValuePreferences } from '../../ldp/representation/RepresentationPreferences';
 import { getLoggerFor } from '../../logging/LogUtil';
-import { InternalServerError } from '../../util/errors/InternalServerError';
-import { matchesMediaType } from './ConversionUtil';
+import { BadRequestHttpError } from '../../util/errors/BadRequestHttpError';
+import { NotImplementedHttpError } from '../../util/errors/NotImplementedHttpError';
+import { cleanPreferences, getBestPreference, getTypeWeight } from './ConversionUtil';
 import type { RepresentationConverterArgs } from './RepresentationConverter';
-import { TypedRepresentationConverter } from './TypedRepresentationConverter';
+import { RepresentationConverter } from './RepresentationConverter';
+import type { TypedRepresentationConverter } from './TypedRepresentationConverter';
+
+type ConverterPreference = ValuePreference & { converter: TypedRepresentationConverter };
+
+/**
+ * A chain of converters that can go from `inTypes` to `outTypes`.
+ * `intermediateTypes` contains the exact types that have the highest weight when going from converter i to i+1.
+ */
+type ConversionPath = {
+  converters: TypedRepresentationConverter[];
+  intermediateTypes: string[];
+  inTypes: ValuePreferences;
+  outTypes: ValuePreferences;
+};
+
+/**
+ * The result of applying a `ConversionPath` to a specific input.
+ */
+type MatchedPath = {
+  path: ConversionPath;
+  inType: string;
+  outType: string;
+  weight: number;
+};
+
+/**
+ * An LRU cache for storing `ConversionPath`s.
+ */
+class LruPathCache {
+  private readonly maxSize: number;
+  // Contents are ordered from least to most recently used
+  private readonly paths: ConversionPath[] = [];
+
+  public constructor(maxSize: number) {
+    this.maxSize = maxSize;
+  }
+
+  /**
+   * Add the given path to the cache as most recently used.
+   */
+  public add(path: ConversionPath): void {
+    this.paths.push(path);
+    if (this.paths.length > this.maxSize) {
+      this.paths.shift();
+    }
+  }
+
+  /**
+   * Find a path that can convert the given type to the given preferences.
+   * Note that this finds the first matching path in the cache,
+   * not the best one, should there be multiple results.
+   * In practice this should almost never be the case though.
+   */
+  public find(inType: string, outPreferences: ValuePreferences): MatchedPath | undefined {
+    // Last element is most recently used so has more chance of being the correct one
+    for (let i = this.paths.length - 1; i >= 0; --i) {
+      const path = this.paths[i];
+      // Check if `inType` matches the input and `outPreferences` the output types of the path
+      const match = this.getMatchedPath(inType, outPreferences, path);
+      if (match) {
+        // Set matched path to most recent result in the cache
+        this.paths.splice(i, 1);
+        this.paths.push(path);
+        return match;
+      }
+    }
+  }
+
+  /**
+   * Calculates the weights and exact types when using the given path on the given type and preferences.
+   * Undefined if there is no match
+   */
+  private getMatchedPath(inType: string, outPreferences: ValuePreferences, path: ConversionPath):
+  MatchedPath | undefined {
+    const inWeight = getTypeWeight(inType, path.inTypes);
+    if (inWeight === 0) {
+      return;
+    }
+    const outMatch = getBestPreference(path.outTypes, outPreferences);
+    if (!outMatch) {
+      return;
+    }
+    return { path, inType, outType: outMatch.value, weight: inWeight * outMatch.weight };
+  }
+}
 
 /**
  * A meta converter that takes an array of other converters as input.
- * It chains these converters by finding intermediate types that are supported by converters on either side.
+ * It chains these converters by finding a path of converters
+ * that can go from the given content-type to the given type preferences.
+ * In case there are multiple paths, the shortest one with the highest weight gets found.
+ * Will error in case no path can be found.
+ *
+ * Generated paths get stored in an internal cache for later re-use on similar requests.
+ * Note that due to this caching `RepresentationConverter`s
+ * that change supported input/output types at runtime are not supported,
+ * unless cache size is set to 0.
+ *
+ * This is not a TypedRepresentationConverter since the supported output types
+ * might depend on what is the input content-type.
+ *
+ * Some suggestions on how this class can be even more optimized should this ever be needed in the future.
+ * Most of these decrease computation time at the cost of more memory.
+ *  - Subpaths that are generated could also be cached.
+ *  - When looking for the next step, cached paths could also be considered.
+ *  - The algorithm could start on both ends of a possible path and work towards the middle.
+ *  - When creating a path, store the list of unused converters instead of checking every step.
  */
-export class ChainedConverter extends TypedRepresentationConverter {
+export class ChainedConverter extends RepresentationConverter {
   protected readonly logger = getLoggerFor(this);
 
   private readonly converters: TypedRepresentationConverter[];
+  private readonly cache: LruPathCache;
 
-  /**
-   * Creates the chain of converters based on the input.
-   * The list of `converters` needs to be at least 2 long.
-   * @param converters - The chain of converters.
-   */
-  public constructor(converters: TypedRepresentationConverter[]) {
+  public constructor(converters: TypedRepresentationConverter[], maxCacheSize = 50) {
     super();
-    if (converters.length < 2) {
-      throw new Error('At least 2 converters are required.');
+    if (converters.length === 0) {
+      throw new Error('At least 1 converter is required.');
     }
     this.converters = [ ...converters ];
-    this.inputTypes = this.first.getInputTypes();
-    this.outputTypes = this.last.getOutputTypes();
+    this.cache = new LruPathCache(maxCacheSize);
   }
 
-  protected get first(): TypedRepresentationConverter {
-    return this.converters[0];
-  }
-
-  protected get last(): TypedRepresentationConverter {
-    return this.converters[this.converters.length - 1];
+  public async canHandle(input: RepresentationConverterArgs): Promise<void> {
+    // Will cache the path if found, and error if not
+    await this.findPath(input);
   }
 
   public async handle(input: RepresentationConverterArgs): Promise<Representation> {
+    const match = await this.findPath(input);
+
+    // No conversion needed
+    if (!this.isMatchedPath(match)) {
+      return input.representation;
+    }
+
+    const { path } = match;
+    this.logger.debug(`Converting ${match.inType} -> ${path.intermediateTypes.join(' -> ')} -> ${match.outType}.`);
+
     const args = { ...input };
-    for (let i = 0; i < this.converters.length - 1; ++i) {
-      const value = await this.getMatchingType(this.converters[i], this.converters[i + 1]);
-      args.preferences = { type: { [value]: 1 }};
-      args.representation = await this.converters[i].handle(args);
+    for (let i = 0; i < path.converters.length - 1; ++i) {
+      const type = path.intermediateTypes[i];
+      args.preferences = { type: { [type]: 1 }};
+      args.representation = await path.converters[i].handle(args);
     }
-    args.preferences = input.preferences;
-    return this.last.handle(args);
+    // For the last converter we set the preferences to the best output type
+    args.preferences = { type: { [match.outType]: 1 }};
+    return path.converters.slice(-1)[0].handle(args);
+  }
+
+  public async handleSafe(input: RepresentationConverterArgs): Promise<Representation> {
+    // This way we don't run `findPath` twice, even though it would be cached for the second call
+    return this.handle(input);
+  }
+
+  private isMatchedPath(path: unknown): path is MatchedPath {
+    return typeof (path as MatchedPath).path === 'object';
   }
 
   /**
-   * Finds the best media type that can be used to chain 2 converters.
+   * Finds a conversion path that can handle the given input,
+   * either in the cache or by generating a new one.
    */
-  protected async getMatchingType(left: TypedRepresentationConverter, right: TypedRepresentationConverter):
-  Promise<string> {
-    const leftTypes = await left.getOutputTypes();
-    const rightTypes = await right.getInputTypes();
-    let bestMatch: { type: string; weight: number } = { type: 'invalid', weight: 0 };
-
-    // Try to find the matching type with the best weight
-    const leftKeys = Object.keys(leftTypes);
-    const rightKeys = Object.keys(rightTypes);
-    for (const leftType of leftKeys) {
-      const leftWeight = leftTypes[leftType];
-      if (leftWeight <= bestMatch.weight) {
-        continue;
-      }
-      for (const rightType of rightKeys) {
-        const rightWeight = rightTypes[rightType];
-        const weight = leftWeight * rightWeight;
-        if (weight > bestMatch.weight && matchesMediaType(leftType, rightType)) {
-          bestMatch = { type: leftType, weight };
-          if (weight === 1) {
-            this.logger.debug(`${bestMatch.type} is an exact match between ${leftKeys} and ${rightKeys}`);
-            return bestMatch.type;
-          }
-        }
+  private async findPath(input: RepresentationConverterArgs): Promise<MatchedPath | ValuePreference> {
+    const type = input.representation.metadata.contentType;
+    if (!type) {
+      throw new BadRequestHttpError('Missing Content-Type header.');
+    }
+    let preferences = input.preferences.type;
+    if (!preferences) {
+      throw new BadRequestHttpError('Missing type preferences.');
+    }
+    preferences = cleanPreferences(preferences);
+
+    const weight = getTypeWeight(type, preferences);
+    if (weight > 0) {
+      this.logger.debug(`No conversion required: ${type} already matches ${Object.keys(input.preferences.type!)}`);
+      return { value: type, weight };
+    }
+
+    // Use a cached solution if we have one.
+    // Note that it's possible that a better one could be generated.
+    // But this is usually highly unlikely.
+    let match = this.cache.find(type, preferences);
+    if (!match) {
+      match = await this.generatePath(type, preferences);
+      this.cache.add(match.path);
+    }
+    return match;
+  }
+
+  /**
+   * Tries to generate the optimal and shortest `ConversionPath` that supports the given parameters,
+   * which will then be used to instantiate a specific `MatchedPath` for those parameters.
+   *
+   * Errors if such a path does not exist.
+   */
+  private async generatePath(inType: string, outPreferences: ValuePreferences): Promise<MatchedPath> {
+    // Generate paths from all converters that match the input type
+    let paths = await this.converters.reduce(async(matches: Promise<ConversionPath[]>, converter):
+    Promise<ConversionPath[]> => {
+      const inTypes = await converter.getInputTypes();
+      if (getTypeWeight(inType, inTypes) > 0) {
+        (await matches).push({
+          converters: [ converter ],
+          intermediateTypes: [],
+          inTypes,
+          outTypes: await converter.getOutputTypes(),
+        });
       }
+      return matches;
+    }, Promise.resolve([]));
+
+    let bestPath = this.findBest(inType, outPreferences, paths);
+    // This will always stop at some point since paths can't have the same converter twice
+    while (!bestPath && paths.length > 0) {
+      // For every path, find all the paths that can be made by adding 1 more converter
+      const promises = paths.map(async(path): Promise<ConversionPath[]> => this.takeStep(path));
+      paths = (await Promise.all(promises)).flat();
+      bestPath = this.findBest(inType, outPreferences, paths);
     }
 
-    if (bestMatch.weight === 0) {
-      this.logger.warn(`No match found between ${leftKeys} and ${rightKeys}`);
-      throw new InternalServerError(`No match found between ${leftKeys} and ${rightKeys}`);
+    if (!bestPath) {
+      this.logger.warn(`No conversion path could be made from ${inType} to ${Object.keys(outPreferences)}.`);
+      throw new NotImplementedHttpError(
+        `No conversion path could be made from ${inType} to ${Object.keys(outPreferences)}.`,
+      );
     }
+    return bestPath;
+  }
+
+  /**
+   * Finds the path from the given list that can convert the given type to the given preferences.
+   * If there are multiple matches the one with the highest result weight gets chosen.
+   * Will return undefined if there are no matches.
+   */
+  private findBest(type: string, preferences: ValuePreferences, paths: ConversionPath[]): MatchedPath | undefined {
+    // Need to use null instead of undefined so `reduce` doesn't take the first element of the array as `best`
+    return paths.reduce((best: MatchedPath | null, path): MatchedPath | null => {
+      const outMatch = getBestPreference(path.outTypes, preferences);
+      if (outMatch && !(best && best.weight >= outMatch.weight)) {
+        // Create new MatchedPath, using the output match above
+        const inWeight = getTypeWeight(type, path.inTypes);
+        return { path, inType: type, outType: outMatch.value, weight: inWeight * outMatch.weight };
+      }
+      return best;
+    }, null) ?? undefined;
+  }
+
+  /**
+   * Finds all converters that could take the output of the given path as input.
+   * For each of these converters a new path gets created which is the input path appended by the converter.
+   */
+  private async takeStep(path: ConversionPath): Promise<ConversionPath[]> {
+    const unusedConverters = this.converters.filter((converter): boolean => !path.converters.includes(converter));
+    const nextConverters = await this.supportedConverters(path.outTypes, unusedConverters);
 
-    this.logger.debug(`${bestMatch.type} is the best match between ${leftKeys} and ${rightKeys}`);
-    return bestMatch.type;
+    // Create a new path for every converter that can be appended
+    return Promise.all(nextConverters.map(async(pref): Promise<ConversionPath> => ({
+      converters: [ ...path.converters, pref.converter ],
+      intermediateTypes: [ ...path.intermediateTypes, pref.value ],
+      inTypes: path.inTypes,
+      outTypes: this.modifyTypeWeights(pref.weight, await pref.converter.getOutputTypes()),
+    })));
+  }
+
+  /**
+   * Creates a new ValuePreferences object, which is equal to the input object
+   * with all values multiplied by the given weight.
+   */
+  private modifyTypeWeights(weight: number, types: ValuePreferences): ValuePreferences {
+    return Object.fromEntries(Object.entries(types).map(([ type, pref ]): [string, number] => [ type, weight * pref ]));
+  }
+
+  /**
+   * Finds all converters in the given list that support taking any of the given types as input.
+   */
+  private async supportedConverters(types: ValuePreferences, converters: TypedRepresentationConverter[]):
+  Promise<ConverterPreference[]> {
+    const promises = converters.map(async(converter): Promise<ConverterPreference | undefined> => {
+      const inputTypes = await converter.getInputTypes();
+      const match = getBestPreference(types, inputTypes);
+      if (match) {
+        return { ...match, converter };
+      }
+    });
+    return (await Promise.all(promises)).filter(Boolean) as ConverterPreference[];
   }
 }


Test patch:
diff --git a/test/integration/GuardedStream.test.ts b/test/integration/GuardedStream.test.ts
index 7db997e26..8ba32961e 100644
--- a/test/integration/GuardedStream.test.ts
+++ b/test/integration/GuardedStream.test.ts
@@ -4,7 +4,10 @@ import {
   readableToString,
   ChainedConverter,
   guardedStreamFrom,
-  RdfToQuadConverter, BasicRepresentation, getLoggerFor,
+  RdfToQuadConverter,
+  BasicRepresentation,
+  getLoggerFor,
+  INTERNAL_QUADS,
 } from '../../src';
 import type { Representation,
   RepresentationConverterArgs,
@@ -22,16 +25,16 @@ class DummyConverter extends TypedRepresentationConverter {
   }
 
   public async getInputTypes(): Promise<Record<string, number>> {
-    return { '*/*': 1 };
+    return { [INTERNAL_QUADS]: 1 };
   }
 
   public async getOutputTypes(): Promise<Record<string, number>> {
-    return { 'custom/type': 1 };
+    return { 'x/x': 1 };
   }
 
   public async handle({ representation }: RepresentationConverterArgs): Promise<Representation> {
     const data = guardedStreamFrom([ 'dummy' ]);
-    const metadata = new RepresentationMetadata(representation.metadata, 'custom/type');
+    const metadata = new RepresentationMetadata(representation.metadata, 'x/x');
 
     return { binary: true, data, metadata };
   }
@@ -47,7 +50,7 @@ describe('A chained converter where data gets ignored', (): void => {
 
   it('does not throw on async crash.', async(): Promise<void> => {
     jest.useFakeTimers();
-    const result = await converter.handleSafe({ identifier, representation: rep, preferences: {}});
+    const result = await converter.handleSafe({ identifier, representation: rep, preferences: { type: { 'x/x': 1 }}});
 
     expect(await readableToString(result.data)).toBe('dummy');
 
diff --git a/test/unit/storage/conversion/ChainedConverter.test.ts b/test/unit/storage/conversion/ChainedConverter.test.ts
index 7fd766223..7902ec54a 100644
--- a/test/unit/storage/conversion/ChainedConverter.test.ts
+++ b/test/unit/storage/conversion/ChainedConverter.test.ts
@@ -1,10 +1,11 @@
 import type { Representation } from '../../../../src/ldp/representation/Representation';
 import { RepresentationMetadata } from '../../../../src/ldp/representation/RepresentationMetadata';
 import type {
-  ValuePreferences,
   RepresentationPreferences,
+  ValuePreferences,
 } from '../../../../src/ldp/representation/RepresentationPreferences';
 import { ChainedConverter } from '../../../../src/storage/conversion/ChainedConverter';
+import { matchesMediaType } from '../../../../src/storage/conversion/ConversionUtil';
 import type { RepresentationConverterArgs } from '../../../../src/storage/conversion/RepresentationConverter';
 import { TypedRepresentationConverter } from '../../../../src/storage/conversion/TypedRepresentationConverter';
 import { CONTENT_TYPE } from '../../../../src/util/Vocabularies';
@@ -28,80 +29,246 @@ class DummyConverter extends TypedRepresentationConverter {
   }
 
   public async handle(input: RepresentationConverterArgs): Promise<Representation> {
+    // Make sure the input type is supported
+    const inType = input.representation.metadata.contentType!;
+    if (!Object.entries(this.inTypes).some(([ range, weight ]): boolean =>
+      weight > 0 && matchesMediaType(range, inType))) {
+      throw new Error(`Unsupported input: ${inType}`);
+    }
+
+    // Make sure we're sending preferences that are actually supported
+    const outType = Object.keys(input.preferences.type!)[0];
+    if (!Object.entries(this.outTypes).some(([ range, weight ]): boolean =>
+      weight > 0 && matchesMediaType(range, outType))) {
+      throw new Error(`Unsupported output: ${outType}`);
+    }
     const metadata = new RepresentationMetadata(input.representation.metadata,
-      { [CONTENT_TYPE]: Object.keys(input.preferences.type!)[0] });
+      { [CONTENT_TYPE]: outType });
     return { ...input.representation, metadata };
   }
 }
 
 describe('A ChainedConverter', (): void => {
-  let converters: TypedRepresentationConverter[];
-  let converter: ChainedConverter;
   let representation: Representation;
   let preferences: RepresentationPreferences;
   let args: RepresentationConverterArgs;
 
   beforeEach(async(): Promise<void> => {
-    converters = [
-      new DummyConverter({ 'text/turtle': 1 }, { 'chain/1': 0.9, 'chain/x': 0.5 }),
-      new DummyConverter({ 'chain/*': 1, 'chain/x': 0.5 }, { 'chain/2': 1 }),
-      new DummyConverter({ 'chain/2': 1 }, { 'internal/quads': 1 }),
-    ];
-    converter = new ChainedConverter(converters);
-
-    const metadata = new RepresentationMetadata('text/turtle');
+    const metadata = new RepresentationMetadata('a/a');
     representation = { metadata } as Representation;
-    preferences = { type: { 'internal/quads': 1 }};
+    preferences = { type: { 'x/x': 1, 'x/*': 0.8 }};
     args = { representation, preferences, identifier: { path: 'path' }};
   });
 
-  it('needs at least 2 converters.', async(): Promise<void> => {
-    expect((): any => new ChainedConverter([])).toThrow('At least 2 converters are required.');
-    expect((): any => new ChainedConverter([ converters[0] ])).toThrow('At least 2 converters are required.');
-    expect(new ChainedConverter([ converters[0], converters[1] ]))
-      .toBeInstanceOf(ChainedConverter);
+  it('needs at least 1 converter.', async(): Promise<void> => {
+    expect((): any => new ChainedConverter([])).toThrow('At least 1 converter is required.');
+    expect(new ChainedConverter([ new DummyConverter({ }, { }) ])).toBeInstanceOf(ChainedConverter);
   });
 
-  it('supports the same inputs as the first converter of the chain.', async(): Promise<void> => {
-    await expect(converter.getInputTypes()).resolves.toEqual(await converters[0].getInputTypes());
+  it('errors if there are no content-type or preferences.', async(): Promise<void> => {
+    args.representation.metadata.contentType = undefined;
+    const converters = [ new DummyConverter({ 'a/a': 1 }, { 'x/x': 1 }) ];
+    const converter = new ChainedConverter(converters);
+    await expect(converter.canHandle(args)).rejects.toThrow('Missing Content-Type header.');
+
+    args.representation.metadata.contentType = 'a/a';
+    args.preferences = { };
+    await expect(converter.canHandle(args)).rejects.toThrow('Missing type preferences.');
   });
 
-  it('supports the same outputs as the last converter of the chain.', async(): Promise<void> => {
-    await expect(converter.getOutputTypes()).resolves.toEqual(await converters[2].getOutputTypes());
+  it('errors if no path can be found.', async(): Promise<void> => {
+    const converters = [ new DummyConverter({ 'a/a': 1 }, { 'x/x': 1 }) ];
+    const converter = new ChainedConverter(converters);
+
+    args.representation.metadata.contentType = 'b/b';
+    await expect(converter.canHandle(args)).rejects
+      .toThrow('No conversion path could be made from b/b to x/x,x/*,internal/*.');
   });
 
-  it('can handle requests with the correct in- and output.', async(): Promise<void> => {
-    await expect(converter.canHandle(args)).resolves.toBeUndefined();
+  it('can handle situations where no conversion is required.', async(): Promise<void> => {
+    const converters = [ new DummyConverter({ 'a/a': 1 }, { 'x/x': 1 }) ];
+    args.representation.metadata.contentType = 'b/b';
+    args.preferences.type = { 'b/*': 0.5 };
+    const converter = new ChainedConverter(converters);
+
+    const result = await converter.handle(args);
+    expect(result.metadata.contentType).toBe('b/b');
   });
 
-  it('errors if the start of the chain does not support the representation type.', async(): Promise<void> => {
-    representation.metadata.contentType = 'bad/type';
-    await expect(converter.canHandle(args)).rejects.toThrow();
+  it('can find paths of length 1.', async(): Promise<void> => {
+    const converters = [ new DummyConverter({ 'a/a': 1 }, { 'x/x': 1 }) ];
+    const converter = new ChainedConverter(converters);
+
+    const result = await converter.handle(args);
+    expect(result.metadata.contentType).toBe('x/x');
   });
 
-  it('errors if the end of the chain does not support the preferences.', async(): Promise<void> => {
-    preferences.type = { 'abc/def': 1 };
-    await expect(converter.canHandle(args)).rejects.toThrow();
+  it('can find longer paths.', async(): Promise<void> => {
+    // Path: a/a -> b/b -> c/c -> x/x
+    const converters = [
+      new DummyConverter({ 'b/b': 0.8, 'b/c': 1 }, { 'c/b': 0.9, 'c/c': 1 }),
+      new DummyConverter({ 'a/a': 0.8, 'a/b': 1 }, { 'b/b': 0.9, 'b/a': 0.5 }),
+      new DummyConverter({ 'd/d': 0.8, 'c/*': 1 }, { 'x/x': 0.9, 'x/a': 1 }),
+    ];
+    const converter = new ChainedConverter(converters);
+
+    const result = await converter.handle(args);
+    expect(result.metadata.contentType).toBe('x/x');
   });
 
-  it('runs the data through the chain.', async(): Promise<void> => {
+  it('will use the best path among the shortest found.', async(): Promise<void> => {
+    // Valid paths: 0 -> 1 -> 2, 3 -> 2, 4 -> 2, 5 -> 2, *6 -> 2*
+    const converters = [
+      new DummyConverter({ 'a/a': 1 }, { 'b/b': 1 }),
+      new DummyConverter({ 'b/b': 1 }, { 'c/c': 1 }),
+      new DummyConverter({ 'c/c': 1 }, { 'x/x': 1 }),
+      new DummyConverter({ '*/*': 0.5 }, { 'c/c': 1 }),
+      new DummyConverter({ 'a/a': 0.8 }, { 'c/c': 1 }),
+      new DummyConverter({ 'a/*': 1 }, { 'c/c': 0.5 }),
+      new DummyConverter({ 'a/a': 1 }, { 'c/c': 0.9 }),
+    ];
+    const converter = new ChainedConverter(converters);
+
+    // Only the best converters should have been called (6 and 2)
+    for (const dummyConverter of converters) {
+      jest.spyOn(dummyConverter, 'handle');
+    }
+    const result = await converter.handle(args);
+    expect(result.metadata.contentType).toBe('x/x');
+    expect(converters[0].handle).toHaveBeenCalledTimes(0);
+    expect(converters[1].handle).toHaveBeenCalledTimes(0);
+    expect(converters[2].handle).toHaveBeenCalledTimes(1);
+    expect(converters[3].handle).toHaveBeenCalledTimes(0);
+    expect(converters[4].handle).toHaveBeenCalledTimes(0);
+    expect(converters[5].handle).toHaveBeenCalledTimes(0);
+    expect(converters[6].handle).toHaveBeenCalledTimes(1);
+  });
+
+  it('will use the intermediate content-types with the best weight.', async(): Promise<void> => {
+    const converters = [
+      new DummyConverter({ 'a/a': 1 }, { 'b/b': 0.8, 'c/c': 0.6 }),
+      new DummyConverter({ 'b/b': 0.1, 'c/*': 0.9 }, { 'd/d': 1, 'e/e': 0.8 }),
+      new DummyConverter({ 'd/*': 0.9, 'e/*': 0.1 }, { 'x/x': 1 }),
+    ];
+    const converter = new ChainedConverter(converters);
+
     jest.spyOn(converters[0], 'handle');
     jest.spyOn(converters[1], 'handle');
-    jest.spyOn(converters[2], 'handle');
-
     const result = await converter.handle(args);
-    expect(result.metadata.contentType).toEqual('internal/quads');
-    expect((converters[0] as any).handle).toHaveBeenCalledTimes(1);
-    expect((converters[1] as any).handle).toHaveBeenCalledTimes(1);
-    expect((converters[2] as any).handle).toHaveBeenCalledTimes(1);
+    expect(result.metadata.contentType).toBe('x/x');
+    let { metadata } = await (converters[0].handle as jest.Mock).mock.results[0].value;
+    expect(metadata.contentType).toBe('c/c');
+    ({ metadata } = await (converters[1].handle as jest.Mock).mock.results[0].value);
+    expect(metadata.contentType).toBe('d/d');
   });
 
-  it('errors if there is no valid chain at runtime.', async(): Promise<void> => {
-    converters = [
-      new DummyConverter({ 'text/turtle': 1 }, { 'chain/1': 0.9, 'chain/x': 0.5 }),
-      new DummyConverter({ 'chain/2': 1 }, { 'internal/quads': 1 }),
+  it('calls handle when calling handleSafe.', async(): Promise<void> => {
+    const converters = [ new DummyConverter({ 'a/a': 1 }, { 'x/x': 1 }) ];
+    const converter = new ChainedConverter(converters);
+    jest.spyOn(converter, 'handle');
+
+    await converter.handleSafe(args);
+    expect(converter.handle).toHaveBeenCalledTimes(1);
+    expect(converter.handle).toHaveBeenLastCalledWith(args);
+  });
+
+  it('caches paths for re-use.', async(): Promise<void> => {
+    const converters = [
+      new DummyConverter({ 'a/a': 0.8 }, { 'b/b': 0.9 }),
+      new DummyConverter({ 'b/b': 0.8 }, { 'x/x': 1 }),
+    ];
+    const converter = new ChainedConverter(converters);
+    let result = await converter.handle(args);
+    expect(result.metadata.contentType).toBe('x/x');
+
+    jest.spyOn(converters[0], 'getInputTypes');
+    jest.spyOn(converters[0], 'getOutputTypes');
+    result = await converter.handle(args);
+    expect(result.metadata.contentType).toBe('x/x');
+    expect(converters[0].getInputTypes).toHaveBeenCalledTimes(0);
+    expect(converters[0].getOutputTypes).toHaveBeenCalledTimes(0);
+  });
+
+  it('removes unused paths from the cache.', async(): Promise<void> => {
+    const converters = [
+      new DummyConverter({ 'a/a': 0.8 }, { 'b/b': 0.9 }),
+      new DummyConverter({ 'b/b': 0.8 }, { 'x/x': 1 }),
+      new DummyConverter({ 'c/c': 0.8 }, { 'b/b': 0.9 }),
+    ];
+    // Cache size 1
+    const converter = new ChainedConverter(converters, 1);
+    let result = await converter.handle(args);
+    expect(result.metadata.contentType).toBe('x/x');
+
+    // Should remove previous path (which contains converter 0)
+    args.representation.metadata.contentType = 'c/c';
+    result = await converter.handle(args);
+    expect(result.metadata.contentType).toBe('x/x');
+
+    jest.spyOn(converters[0], 'getInputTypes');
+    jest.spyOn(converters[0], 'getOutputTypes');
+    args.representation.metadata.contentType = 'a/a';
+    result = await converter.handle(args);
+    expect(result.metadata.contentType).toBe('x/x');
+    expect(converters[0].getInputTypes).not.toHaveBeenCalledTimes(0);
+    expect(converters[0].getOutputTypes).not.toHaveBeenCalledTimes(0);
+  });
+
+  it('keeps the most recently used paths in the cache.', async(): Promise<void> => {
+    const converters = [
+      new DummyConverter({ 'a/a': 1 }, { 'd/d': 1 }),
+      new DummyConverter({ 'b/b': 1 }, { 'd/d': 1 }),
+      new DummyConverter({ 'c/c': 1 }, { 'd/d': 1 }),
+      new DummyConverter({ 'd/d': 1 }, { 'x/x': 1 }),
     ];
-    converter = new ChainedConverter(converters);
-    await expect(converter.handle(args)).rejects.toThrow();
+    // Cache size 2
+    const converter = new ChainedConverter(converters, 2);
+    // Caches path 0
+    await converter.handle(args);
+
+    // Caches path 1
+    args.representation.metadata.contentType = 'b/b';
+    await converter.handle(args);
+
+    // Reset path 0 in cache
+    args.representation.metadata.contentType = 'a/a';
+    await converter.handle(args);
+
+    // Caches path 2 and removes 1
+    args.representation.metadata.contentType = 'c/c';
+    await converter.handle(args);
+
+    jest.spyOn(converters[0], 'getInputTypes');
+    jest.spyOn(converters[1], 'getInputTypes');
+    jest.spyOn(converters[2], 'getInputTypes');
+
+    // Path 0 and 2 should be cached now
+    args.representation.metadata.contentType = 'a/a';
+    await converter.handle(args);
+    expect(converters[0].getInputTypes).toHaveBeenCalledTimes(0);
+    args.representation.metadata.contentType = 'c/c';
+    await converter.handle(args);
+    expect(converters[2].getInputTypes).toHaveBeenCalledTimes(0);
+    args.representation.metadata.contentType = 'b/b';
+    await converter.handle(args);
+    expect(converters[1].getInputTypes).not.toHaveBeenCalledTimes(0);
+  });
+
+  it('does not use cached paths that match content-type but not preferences.', async(): Promise<void> => {
+    const converters = [
+      new DummyConverter({ 'a/a': 1 }, { 'b/b': 1 }),
+      new DummyConverter({ 'b/b': 1 }, { 'x/x': 1 }),
+      new DummyConverter({ 'a/a': 1 }, { 'c/c': 1 }),
+      new DummyConverter({ 'c/c': 1 }, { 'y/y': 1 }),
+    ];
+    const converter = new ChainedConverter(converters);
+
+    // Cache a-b-x path
+    await converter.handle(args);
+
+    // Generate new a-c-y path
+    args.preferences.type = { 'y/y': 1 };
+    const result = await converter.handle(args);
+    expect(result.metadata.contentType).toBe('y/y');
   });
 });